2021-08-01 acwing算法基础课 动态规划
2021/8/3 20:05:57
本文主要是介绍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算法基础课 动态规划的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享