1269:【例9.13】庆功会 http://ybt.ssoier.cn:8088/problem_show.php?pid=1269
#include<bits/stdc++.h> using namespace std; int n,m; int w[503],v[503],s[503]; int dp[6007]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>w[i]>>v[i]>>s[i]; } for(int i=1;i<=n;i++){ for(int k=1;k<=s[i];k++){ for(int j=m;j>=0;j--){ if(j-w[i]>=0&&dp[j-w[i]]+v[i]>dp[j]){ dp[j]=dp[j-w[i]]+v[i]; } } } } cout<<dp[m]; return 0; }
1270:【例9.14】混合背包 http://ybt.ssoier.cn:8088/problem_show.php?pid=1270
#include<bits/stdc++.h> using namespace std; int n,m; int w[31],v[31],s[31]; int dp[203]; int main(){ cin>>m>>n; for(int i=1;i<=n;i++){ cin>>w[i]>>v[i]>>s[i]; if(s[i]==0)s[i]=m/w[i]+5; } for(int i=1;i<=n;i++){ for(int k=1;k<=s[i];k++){ for(int j=m;j>=0;j--){ if(j-w[i]>=0&&dp[j-w[i]]+v[i]>dp[j]){ dp[j]=dp[j-w[i]]+v[i]; } } } } cout<<dp[m]; return 0; }
1258:【例9.2】数字金字 http://ybt.ssoier.cn:8088/problem_show.php?pid=1258
枚举10% 记忆化+递归100% dp100%
#include<bits/stdc++.h> using namespace std; long long R; long long a[1003][1005]; int main(){ cin>>R; for(long long i=1;i<=R;i++){ for(long long j=1;j<=i;j++){ cin>>a[i][j]; } } long long maxx=0; for(long long i=0;i<pow(2,R-1);i++){ long long n=i; long long s=a[1][1],x=1; for(long long j=2;j<=R;j++){ if(n%2==1)x++; n=n/2; s+=a[j][x]; } maxx=max(maxx,s); } cout<<maxx; return 0; } /* 10%枚举 未通过 10分 测试点1: 答案正确 628KB 4MS 测试点2: 答案错误 768KB 9MS 测试点3: 答案错误 1012KB 7MS 测试点4: 答案错误 1536KB 8MS 测试点5: 运行超时 3548KB 995MS 测试点6: 答案错误 5160KB 55MS 测试点7: 答案错误 6248KB 78MS 测试点8: 答案错误 6772KB 125MS 测试点9: 答案错误 7476KB 101MS 测试点10: 答案错误 7500KB 101MS */
#include<bits/stdc++.h> using namespace std; int R; int a[1003][1003]; int p[1003][1003]; int f(int n,int m){ if(n==R){ p[n][m]=a[n][m]; return a[n][m]; } int l1,l2; if(p[n+1][m]!=0)l1=p[n+1][m]; else l1=f(n+1,m); if(p[n+1][m+1]!=0)l2=p[n+1][m+1]; else l2=f(n+1,m+1); p[n][m]=a[n][m]+max(l1,l2); return p[n][m]; } int main(){ cin>>R; for(int i=1;i<=R;i++){ for(int j=1;j<=i;j++){ cin>>a[i][j]; } } cout<<f(1,1); return 0; }
/*
记忆化+递归100%
*/
#include<bits/stdc++.h> using namespace std; int R; int a[1005][1005],dp[1005][1005]; int main(){ cin>>R; for(int i=1;i<=R;i++){ for(int j=1;j<=i;j++){ cin>>a[i][j]; } } for(int i=1;i<=R;i++){ for(int j=1;j<=i;j++){ dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j]; } } int ans=0; for(int i=1;i<=R;i++){ ans=max(dp[R][i],ans); } cout<<ans; return 0; }
/*
dp100%
*/
1271:【例9.15】潜水员 http://ybt.ssoier.cn:8088/problem_show.php?pid=1271
#include<bits/stdc++.h> using namespace std; int m,n,k; int O2[1003],N2[1003],w[1003]; int f[25][85]; int main(){ cin>>m>>n; cin>>k; memset(f,0x3f3f3f3f,sizeof(f)); f[0][0]=0; for(int i=1;i<=k;i++){ cin>>O2[i]>>N2[i]>>w[i]; } for(int a=1;a<=k;a++){ for(int i=m;i>=0;i--){ for(int j=n;j>=0;j--){ if(i>=O2[a]&&j>=N2[a])f[i][j]=min(f[i][j],f[i-O2[a]][j-N2[a]]+w[a]); else if(i>=O2[a])f[i][j]=min(f[i][j],f[i-O2[a]][0]+w[a]); else if(j>=N2[a])f[i][j]=min(f[i][j],f[0][j-N2[a]]+w[a]); else f[i][j]=min(f[i][j],f[0][0]+w[a]); } } } cout<<f[m][n]; return 0; } /* f[i][j]=min(f[i][j],f[i-O2[a]][j-N2[a]]+w[a]); */标签:22,int,cin,long,morning,1003,O2,dp From: https://www.cnblogs.com/zangqy/p/17572951.html