LZH_LOVE_ZRG @ 2021-03-24 20:11:24
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=70;
ll f[32010];
int s[N][3];
int v[N],w[N],b[N];
int val(int x){
return w[x]*v[x];
}
int main(){
int m; cin>>m;
int n; cin>>n;
for(int i=1,x;i<=n;i++){
cin>>w[i]>>v[i]>>x;
if(x) s[x][++s[x][0]]=i;
else b[i]=1;
}
for(int i=1,s1,s2;i<=n;i++,s1=s2=0){
if(!b[i]) continue;
if(s[i][1]) s1=s[i][1];
if(s[i][2]) s2=s[i][2];
for(int j=m;j>=w[i];j--){
if(j>=w[i])
f[j]=max(f[j],f[j-w[i]]+val(i));
if(s1&&j>=w[i]+w[s1])
f[j]=max(f[j],f[j-w[i]-w[s1]]+val(i)+val(s1));
if(s2&&j>=w[i]+w[s2])
f[j]=max(f[j],f[j-w[i]-w[s2]]+val(i)+val(s2));
if(s1&&s2&&j>=w[i]+w[s1]+w[s2])
f[j]=max(f[j],f[j-w[i]-w[s1]-w[s2]]+val(i)+val(s1)+val(s2));
}
}
cout<<f[m];
return 0;
}
蒟蒻写码不易,求调。
附
输入
1000 5
300 5 0
400 2 0
300 5 2
300 4 2
600 4 0
输出
3900