C/C++教程
2021-08-01 acwing算法基础课 动态规划
本文主要是介绍2021-08-01 acwing算法基础课 动态规划，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
AcWing 2. 01背包问题
1.题意：
2.题解：
3.ac代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
const int N=1e6+10;
using namespace std;
int n,m;
int f[N];
int v[N],w[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
cout<<f[m]<<endl;
}
AcWing 3. 完全背包问题
1.题意：
2.题解：
3.ac代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
const int N=1e6+10;
using namespace std;
int n,m;
int f[N];
int v[N],w[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>> v[i]>>w[i];
}
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
cout<<f[m]<<endl;
}
AcWing 4. 多重背包问题
1.题意：
2.题解：
3.ac代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
const int N=1e6+10;
using namespace std;
int n,m;
int f[200][200];
int v[N],w[N],s[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>> v[i]>>w[i]>>s[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=s[i]&&k*v[i]<=j;k++){
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);//!!是f[i][j]
}
}
}
cout<<f[n][m]<<endl;
}
AcWing 5. 多重背包问题 II
1.题意：
2.题解：
3.ac代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
const int N=1e6+10;
using namespace std;
int n,m;
int f[N];
int v[N],w[N];
int main(){
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++){
int a,b,s;
cin>>a>>b>>s;
int k=1;
while(k<=s){
cnt++;
v[cnt]=k*a;
w[cnt]=k*b;
s-=k;
k*=2;
}
if(s>0){
cnt++;
v[cnt]=s*a;
w[cnt]=s*b;
}
}
for(int i=1;i<=cnt;i++){
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
}
AcWing 9. 分组背包问题
1.题意：
2.题解：
3.ac代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
const int N=1e6+10;
using namespace std;
int s[N],f[N],v[200][200],w[200][200];
int main(){
int n,m;
cin>>n>>m;
int t=1;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int j=0;j<s[i];j++){
cin>>v[i][j]>>w[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j--){
for(int k=0;k<s[i];k++){
if(j>=v[i][k]){
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
}
}
}
}
cout<<f[m]<<endl;
}
AcWing 898. 数字三角形
1.题意：
2.题解：
3.ac代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
const int N=1e6+10;
using namespace std;
int n,m;
int a[600][600];
int dp[600][600];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
// for(int i=0;i<=n;i++){
// for(int j=0;j<=n;j++){
// dp[i][j]=-Inf;
// }
// }
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
a[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1]);
}
}
cout<<a[1][1]<<endl;
}
AcWing 895. 最长上升子序列
1.题意：
2.题解：
3.ac代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
const int N=1e6+10;
using namespace std;
int n,m;
int a[N];
int f[N];
//const Inf=0x3f3f3f3f;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(a[j]<a[i])
f[i]=max(f[j]+1,f[i]);
}
}
int res=0;
for(int i=1;i<=n;i++){
res=max(res,f[i]);
}
cout<<res<<endl;
}
AcWing 896. 最长上升子序列 II
1.题意：
2.题解：
注：l和r len初始值都为0
二分，若l=mid，那么求mid时要+1
3.ac代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
const int N=1e6+10;
const int INF=0x3f3f3f3f;
int a[N],q[N];
using namespace std;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
q[0]=-INF;
int len=0;
for(int i=1;i<=n;i++){
int l=0;
int r=len;
while(l<r){
int mid=l+r+1>>1;
if(q[mid]<a[i]) l=mid;
else r=mid-1;
}
len=max(len,r+1);
q[r+1]=a[i];
}
cout<<len<<endl;
}
AcWing 897. 最长公共子序列
1.题意：
2.题解：
3.ac代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
const int N=1e6+10;
using namespace std;
int n,m;
char a[N],b[N];
int f[N];
int dp[2000][2000];
//const Inf=0x3f3f3f3f;
int main(){
// int n;
cin>>n>>m;
scanf("%s%s",a+1,b+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i]==b[j]){
dp[i][j]=dp[i-1][j-1]+1;
}else {
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
cout<<dp[n][m]<<endl;
}
AcWing 902. 最短编辑距离
1.题意：
2.题解：
3.ac代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N=1e6+10;
const int INF=0x3f3f3f3f;
char a[N],b[N];
int f[2010][2010];
int main(){
int n,m;
cin>>n;
scanf("%s",a+1);
cin>>m;
scanf("%s",b+1);
for(int i=0;i<=n;i++) f[i][0]=i;
for(int i=0;i<=m;i++) f[0][i]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=min(f[i][j-1],f[i-1][j])+1;
f[i][j]=min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]));
}
}
cout<<f[n][m];
}
AcWing 899. 编辑距离
1.题意：
2.题解：
3.ac代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N=1e6+10;
const int INF=0x3f3f3f3f;
char a[N],b[N];
int f[2010][2010];
int cmp(char a[],char b[]){
int la=strlen(a+1),lb=strlen(b+1);
for(int i=0;i<=la;i++) f[i][0]=i;
for(int j=0;j<=lb;j++) f[0][j]=j;
for(int i=1;i<=la;i++){
for(int j=1;j<=lb;j++){
f[i][j]=min(f[i-1][j],f[i][j-1])+1;
f[i][j]=min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]));
}
}
return f[la][lb];
}
char str[N][12];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%s",str[i]+1);
}
for(int i=1;i<=m;i++){
char s[12];
scanf("%s",s+1);
int t;
int res=0;
cin>>t;
for(int j=1;j<=n;j++){
int ans=cmp(str[j],s);
if(ans<=t) res++;
}
cout<<res<<endl;
}
}
AcWing 282. 石子合并
1.题意：
2.题解：
3.ac代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
const int N=1e6+10;
using namespace std;
int n,m;
int a[N],s[N];
int f[N];
int dp[2000][2000];
const int INF=0x3f3f3f3f;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
for(int len=2;len<=n;len++){
for(int i=1;i<=n-len+1;i++){
int j=i+len-1;
dp[i][j]=INF;
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
}
}
}
cout<<dp[1][n]<<endl;
}
AcWing 900. 整数划分
1.题意：
2.题解：
3.ac代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N=1e6+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
char a[N],b[N];
int f[N];
int n;
int main(){
cin>>n;
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
f[j]=(f[j]+f[j-i])%mod;
}
}
cout<<f[n]<<endl;
}
AcWing 338. 计数问题
1.题意：
2.题解：
分类讨论！！！
3.ac代码：
#include<bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include<set>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int get(vector<int> num,int l,int r){
int res=0;
for(int i=l;i>=r;i--){
res=res*10+num[i];
}
return res;
}
int pow10(int n){
int res=1;
while(n){
res=res*10;
n--;
}
return res;
}
int count(int n,int x){
if(!n) return 0;
vector<int> num;
while(n){
num.push_back(n%10);
n=n/10;
}
n=num.size();
int res=0;
for(int i=n-1-!x;i>=0;i--){
if(i<n-1){
res+=get(num,n-1,i+1)*pow10(i);
if(!x) res-=pow10(i);
}
if(num[i]==x) res+=get(num,i-1,0)+1;
else if(num[i]>x) res+=pow10(i);
}
return res;
}
int main(){
int a,b;
while(cin>>a>>b,a||b){
if(a>b) swap(a,b);
for(int i=0;i<10;i++){
cout<<count(b,i)-count(a-1,i)<<" ";
}
cout<<endl;
}
}
AcWing 291. 蒙德里安的梦想
1.题意：
2.题解：
所有方案数=所有合法的横方格放置方案数
f[i][j]代表第i列是否有1x2方格中第二个方格的情况
f[i][j]=f[i-1][k]和 ,k=0,k=1<<n,前一个方案的情况导致了下一个方案
合法：
1.前一列和当前列不能有重叠的1，因为f[i][j]代表从前一列开始到第i列结束的1x2方格，在i-1列，她是0，到第i列给他安上了1x2的方格，
2.前一列剩余的连续空格必须是偶数个，(这个剩余指的是+到该列为止的1x2方格），所以用st[i|j]，i和j中所有1的并才是前一列真正剩余的空格情况
所以求时分两个方面，先找出所有符合2的情况用st存，st总共有1<<n种情况，
遍历两列各有1<<n种情况，看满足1吗，即i&j ==0,再看满足2吗即st[i|j],若满足，则将当前的j（代表前一列的情况）存入state【i】
从1到m遍历，对每一个j（0~1<<n)求其方案数和
f[0][0]代表第0列没有从前面列伸出来的方块，此时没有横方块，也是一种方案
f【m][0]代表实际上的m+1列即前m列都已合法填过且符合要求，不会有伸到第m+1的方格，显然是答案。
3.ac代码：
#include<bits/stdc++.h>
#include<vector>
using namespace std;
typedef long long ll;
const int N=12;const int M=1<<N;
ll f[N][M];
vector<int> state[M];
bool st[M];
int main(){
int n,m;
while(cin>>n>>m,n||m){
for(int i=0;i<1<<n;i++){
bool iv=true;
int cnt=0;
for(int j=0;j<n;j++){
if((i>>j)&1){
if(cnt&1){
iv=false;
break;
}
cnt=0;
}else{
cnt++;
}
}
if(cnt&1) iv=false;
st[i]=iv;
}
for(int i=0;i<1<<n;i++){
state[i].clear();
for(int j=0;j<1<<n;j++){
if((i&j)==0&&st[i|j]){
state[i].push_back(j);
}
}
}
memset(f,0,sizeof f);
f[0][0]=1;
for(int i=1;i<=m;i++){
for(int j=0;j<1<<n;j++){
for(auto k:state[j]){
f[i][j]+=f[i-1][k];
}
}
}
cout<<f[m][0]<<endl;
}
}
AcWing 91. 最短Hamilton路径
1.题意：
2.题解：
注意±的优先级高于位运算，位运算优先级高于&
3.ac代码：
#include<bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include<set>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
int n;
const int N=21;
int f[1<<N][N];
int w[N][N];
int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>w[i][j];
}
}
memset(f,0x3f,sizeof f);
f[1][0]=0;
for(int i=0;i<1<<n;i++){
for(int j=0;j<n;j++){
if(i>>j&1){
for(int k=0;k<n;k++){
if((i>>k) &1){
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
}
}
}
}
}
cout<<f[(1<<n)-1][n-1]<<endl;
}
AcWing 285. 没有上司的舞会
1.题意：
2.题解：
3.ac代码：
#include<bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include<set>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int h[N],e[N],ne[N],idx;
int happy[N];
bool fa[N];
int f[N][2];
void add(int a,int b){
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u){
f[u][1]=happy[u];
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
dfs(j);
f[u][0]+=max(f[j][1],f[j][0]);
f[u][1]+=f[j][0];
}
}
int isfa(int n){
for(int i=1;i<=n;i++){
if(fa[i]==false)
return i;
}
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>happy[i];
memset(h,-1,sizeof h);
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
add(b,a);
fa[a]=true;
}
int root=isfa(n);
dfs(root);
int ans=max(f[root][0],f[root][1]);
cout<<ans<<endl;
}
AcWing 901. 滑雪
1.题意：
2.题解：
3.ac代码：
#include<bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include<set>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int f[301][401];
int h[301][301];
int r,c;
int dp(int x,int y){
int &v=f[x][y];
if(v!=-1){
return v;
}
v=1;
for(int i=0;i<4;i++){
int a=x+dx[i];
int b=y+dy[i];
if(a>=1&&a<=r&&b>=1&&b<=c&&h[x][y]>h[a][b]){
v=max(v,dp(a,b)+1);
}
}
return v;
}
int main(){
cin>>r>>c;
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
cin>>h[i][j];
}
}
memset(f,-1,sizeof f);
int res=0;
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
res=max(res,dp(i,j));
}
}
cout<<res<<endl;
}
这篇关于2021-08-01 acwing算法基础课 动态规划的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享07-05
-
idea控制台，日志太多，导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享07-05
-
The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享07-05
-
怎么清理项目缓存-icode9专业技术文章分享07-05
-
安装 Eyoucms详细图文教程-icode9专业技术文章分享07-04
-
ueditor 复制文章时，图片的链接是一个下载图片地址，该如何处理？-icode9专业技术文章分享07-04
-
怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享07-04
-
具有编译功能的系统make后，无法ssh连接-icode9专业技术文章分享07-04
-
make后如何升级ssh-icode9专业技术文章分享07-04
-
微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享07-03
-
微信支付提示订单号重复-icode9专业技术文章分享07-03
-
微服务启动nacos注册上去了，但是一直没有收到请求-icode9专业技术文章分享07-02
-
如何检查文件的编码格式-icode9专业技术文章分享07-02
-
sublime 更改编码格式-icode9专业技术文章分享07-02
-
uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享06-30
栏目导航
