魔塔哈奇 @ 2017-09-29 20:30:07
#include <bits/stdc++.h>
using namespace std;
int n, m;
int v[70], p[70], q[70], imp[70], bp[32010];
int main(){
cin>> n>> m;
for(int i=1; i<=m; i++){
cin>> v[i]>> p[i]>> q[i];
imp[i]=v[i]*p[i];
}
memset(bp, 0, sizeof(bp));
for(int i=1; i<=m; i++)
{
if(q[i]!=0) continue;
for(int j=n; j>=v[i]; j--)
{
if(bp[j-v[i]]+imp[i]>bp[j]) //比较放主件与不放
{
bp[j]=bp[j-v[i]]+imp[i];
int tmp[2], now=0;
for(int k=1; k<=m; k++)
{
if(q[k]!=i) continue;
if(j<v[k]+v[i]) continue;
tmp[now++]=k;
if(now==2) break;
}
if(now>0)
bp[j]=max(bp[j-v[i]-v[tmp[0]]]+imp[i]+imp[tmp[0]], bp[j]); //比较放第一个附件和不放附件
if(now>1){
bp[j]=max(bp[j-v[i]-v[tmp[1]]]+imp[i]+imp[tmp[1]], bp[j]); //比较放第二个附件和不放附件
if(j>=v[i]+v[tmp[0]]+v[tmp[1]])
bp[j]=max(bp[j-v[i]-v[tmp[0]]-v[tmp[1]]]+imp[i]+imp[tmp[0]]+imp[tmp[1]], bp[j]); // 比较放第一个和第二个附件和不放附件
}
}
}
}
cout<< bp[n];
return 0;
}