题意:略。
题记:每一个从者和礼装都当成是一个物品,那么物品只有选和不选两种情况。(背包的思想)
dp[i][j][k][l]表示前i个物品cost值为j选了k个从者和l件礼装。
在循环时可以把数组第一维优化掉(跟背包问题一样优化)。
在输入从者时:
dp[j][k][0]=max(dp[j][k][0],dp[j-y][k-1][0]+x);
在输入从者时:
dp[j][k][l]=max(dp[j][k][l],dp[j-y][k][l-1]+x);
在每次计算时用ans去取最大值即是答案。
#include<bits/stdc++.h> using namespace std; int dp[200][10][10]; int main(){ int n,m,d; cin>>n>>m>>d; int x,y,ans=0; for(int i=1;i<=n;i++){ cin>>x>>y; for(int j=d;j>=y;j--){//枚举cost值 for(int k=1;k<=5;k++){//枚举从者 dp[j][k][0]=max(dp[j][k][0],dp[j-y][k-1][0]+x); ans=max(ans,dp[j][k][0]); } } } for(int i=1;i<=m;i++){ cin>>x>>y; for(int j=d;j>=y;j--){//枚举cost值 for(int k=1;k<=5;k++){//枚举从者 for(int l=1;l<=k;l++){//枚举礼装 dp[j][k][l]=max(dp[j][k][l],dp[j-y][k][l-1]+x); ans=max(ans,dp[j][k][l]); } } } } cout<<ans<<endl; return 0; }