JiJiZi @ 2023-02-14 16:02:21
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3.2* 10000 + 5,MAXM = 65;
int n,m;
int f[MAXN];
int cnt[MAXM],w[MAXM],v[MAXM];
int t[MAXM][MAXM];
int al[MAXM];
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i++){
int k;
scanf("%d%d%d",&w[i],&v[i],&k);
if(k!=0) al[i]++,cnt[k]++;t[k][cnt[k]] = i;
}
for(int i = 1;i <= m;i++){
if(al[i] != 0) continue;
for(int j = n;j >= w[i];j--){
f[j] = max(f[j],f[j-w[i]]+w[i]*v[i]);
if((w[i] + w[t[i][1]]) <= j) f[j] = max(f[j],f[j-w[i]-w[t[i][1]]] +w[t[i][1]]*v[t[i][1]]+w[i]*v[i]);
if((w[i] + w[t[i][2]]) <= j) f[j] = max(f[j],f[j-w[i]-w[t[i][2]]] +w[t[i][2]]*v[t[i][1]]+w[i]*v[i]);
if((w[i] + w[t[i][1]] + w[t[i][2]]) <= j) f[j] = max(f[j],f[j-w[i]-w[t[i][1]] - w[t[i][2]]] +w[t[i][2]]*v[t[i][2]] +w[t[i][1]]*v[t[i][1]]+w[i]*v[i]);
}
}
printf("%d",f[n]);
return 0;
}
不知道为什么测试点8不能通过,有好心人分享下测试点8的数据嘛。
by JiJiZi @ 2023-02-14 16:06:10
把附件和主体讨论的时候写的有点乱。其他测试点都能过,今天一次下载机会已经没有了,呜呜呜~