Wildchesse @ 2023-06-01 19:58:30
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define MAXM 65
#define MAXN 32005
using namespace std;
int n,m,v[MAXM],p[MAXM],q[MAXM],f[MAXN],nx[MAXN][5],ans=-1e9,pans=-1e9;
signed main(){
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>v[i]>>p[i]>>q[i];
if(q[i]!=0 and !nx[q[i]][1]){
nx[q[i]][1]=i;
}
else if(q[i]!=0 and !nx[q[i]][2]){
nx[q[i]][2]=i;
}
}
for(int i=1;i<=m;i++){
if(q[i]){
continue;
}
for(int j=n;j>=v[i];j--){
pans=max(f[j],f[j-v[i]]+v[i]*p[i]);
if(nx[i][1]!=0 and j>=v[i]+v[nx[i][1]]){
pans=max(pans,f[j- v[i] - v[nx[i][1]]]
+ v[i]*p[i] + v[nx[i][1]]*p[nx[i][1]] );
}
if(nx[i][2]!=0 and j>=v[i]+v[nx[i][2]]){
pans=max(pans,f[j-v[i] - v[nx[i][2]]]
+ v[i]*p[i] + v[nx[i][2]]*p[nx[i][2]]);
}
if(nx[i][2]!=0 and j>=v[i]+v[nx[i][1]]+v[nx[i][2]]){
pans=max(pans,f[j-v[i] - v[nx[i][1]] - v[nx[i][2]]]
+ v[i]*p[i] + v[nx[i][1]]*p[nx[i][1]] +v[nx[i][2]]*p[nx[i][21]]);
}
f[j]=pans;
}
}
cout<<f[n];
return 0;
}
对照题解,认为错误出在存储方式上但找不出来为什么会错,恳请各位大佬能不能帮帮这位蒟蒻捏QWQ
by Wildchesse @ 2023-06-01 20:01:51
或者给一组m<6的hack也行
by ninji @ 2023-06-05 21:36:39
@Wildchesse
hack
2000 5
100 3 0
1000 3 1
400 5 0
300 5 0
1400 2 3
by ninji @ 2023-06-05 21:37:03
@Wildchesse 此题有坑!!!
by ninji @ 2023-06-05 21:39:02
hack
2000 5
100 3 0
1000 3 1
400 5 0
300 5 0
1400 2 3
ans:6800