令表示在前个魔法上花费个金币的最大效果值,则有:
题目还需要让我们输出方案,故我们使用结构体记录数组,具体的,代表最大效果值,代表达到最大效果值时第个魔法的等级
当存在使得取最大值时,将采用的方案,并购买第个魔法级
故将复制到,并将赋值为;
题目要求若有多种方案时输出金币消耗最小的,故我们需要找到最小的使得,并输出
代码:
#include<bits/stdc++.h>
using namespace std;
struct node{
int x;
int ans[105];
}dp[105][505];
int p[105],c[105],v[105][55],ans[105];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>c[i]>>p[i];
for(int j=1;j<=p[i];j++){
cin>>v[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int kpos=0;
for(int k=0;k<=p[i]&&k*c[i]<=j;k++){
if(dp[i-1][j-k*c[i]].x+v[i][k]>dp[i][j].x){
dp[i][j].x=dp[i-1][j-k*c[i]].x+v[i][k];
kpos=k;
}
}
for(int k=1;k<=i-1;k++){
dp[i][j].ans[k]=dp[i-1][j-kpos*c[i]].ans[k];
}
dp[i][j].ans[i]=kpos;
}
}
while(dp[n][m].x==dp[n][m-1].x){
m--;
}
cout<<dp[n][m].x<<endl;
for(int i=1;i<=n;i++){
cout<<dp[n][m].ans[i]<<endl;
}
return 0;
}