啊啊啊啊 调了几个小时,帮帮我吧
参考的这篇题解,我的代码里的数组名设置都遵从这篇题解,除了 n 和 m 的定义遵照了题面(题解的作者好像把它们搞反了)
本人获得了30分,第一个WA的点是#3
#3数据如下:
4500 12
100 3 0
400 5 0
300 5 0
1400 2 0
500 2 0
800 2 4
1400 5 4
300 5 0
1400 3 8
500 2 0
1800 4 0
440 5 10
16700
18200
我的代码:
#include<iostream>
#include<algorithm>
#define maxm 65
#define maxn 32005
using namespace std;
int maxx(int x1,int x2,int x3,int x4,int x5){
return max(x1,max(x2,max(x3,max(x4,x5))));
}
int n,m,cost[maxm],w[maxm],f[maxn],c[maxm][3]; //n:volume m:num
int main(){
cin>>n>>m;
n=n/10;
for(int i=1;i<=m;i++){
int temp;
cin>>temp;
cost[i]=temp/10;
cin>>temp;
w[i]=temp*cost[i];
cin>>temp;
c[temp][++c[temp][0]]=i;
}
for(int i=1;i<=c[0][0];i++)
for(int j=n;j>=cost[c[0][i]];j--){
f[j]=maxx(f[j],(j-cost[c[0][i]])>=0?f[j-cost[c[0][i]]]+w[c[0][i]]:0,(j-cost[c[c[0][i]][1]]-cost[c[0][i]])>=0?f[j-cost[c[c[0][i]][1]]-cost[c[0][i]]]+w[c[c[0][i]][1]]+w[c[0][i]]:0,(j-cost[c[c[0][i]][2]]-cost[c[0][i]])>=0?f[j-cost[c[c[0][i]][2]]-cost[c[0][i]]]+w[c[c[0][i]][2]]+w[c[0][i]]:0,(j-cost[c[c[0][i]][1]]-cost[c[c[0][i]][2]]-cost[c[0][i]])>=0?f[j-cost[c[c[0][i]][1]]-cost[c[c[0][i]][2]]-cost[c[0][i]]]+w[c[c[0][i]][1]]+w[c[c[0][i]][2]]+w[c[0][i]]:0);
}
for(int i=1;i<=n;i++)cout<<f[i]<<" ";
cout<<endl;
cout<<(f[n]*10);
return 0;
}