MWL_wma @ 2023-12-24 16:21:53
不知道哪里错了,玄关,谢谢
#include<bits/stdc++.h>
using namespace std;
int n,m;
int s[62][4],v[62][4],f[32000];
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(!c){
s[i][1]=a,v[i][1]=a*b;
s[i][0]=1,v[i][0]=1;
}else{
s[c][0]++,
s[c][s[c][0]]=s[c][1]+a;
v[c][0]++,
v[c][v[c][0]]=v[c][1]+a*b;
--n,--i;
}
}
for(int i=1;i<=n;i++){
for(int j=m;j>=s[i][1];j--){
int mx=f[j-s[i][1]]+v[i][1];
if(j>=s[i][1]+s[i][2])
mx=max(mx,f[j-s[i][1]-s[i][2]]+v[i][1]+v[i][2]);
if(j>=s[i][1]+s[i][3])
mx=max(mx,f[j-s[i][1]-s[i][3]]+v[i][1]+v[i][3]);
if(j>=s[i][1]+s[i][2]+s[i][3])
mx=max(mx,f[j-s[i][1]-s[i][2]-s[i][3]]+v[i][1]+v[i][2]+v[i][3]);
f[j]=mx;
}
//printf("%d\n",f[m]);
}
printf("%d",f[m]);
return 0;
}
by MWL_wma @ 2023-12-24 16:22:27
AC 1#,其他 WA
by TangyixiaoQAQ @ 2023-12-24 22:10:31
@yma_y_wma
int mx=f[j-s[i][1]]+v[i][1];
这样判断上一步的最优解又去哪里了呢?
顺序结构特有的可爱(ex)数据结构,导致你这里用mx
就无法更新。
所以建议转移的时候直接用f[j]
这个输入建议改一改
for(int i=1;i<=n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(!c){
s[i][1]=a,v[i][1]=a*b;
s[i][0]=1,v[i][0]=1;
}else{
s[c][0]++,
s[c][s[c][0]]=s[c][1]+a;
v[c][0]++,
v[c][v[c][0]]=v[c][1]+a*b;
--n,--i;
}
}
尤其是
--n,--i;
by MWL_wma @ 2023-12-24 22:39:05
@TangyixiaoQAQ 感觉你很强,说得 very 有理,但是好像过不了(
by TangyixiaoQAQ @ 2023-12-25 16:04:04
@yma_y_wma 输入改了吗