world_romantic_xebec @ 2018-10-03 12:02:12
#include <bits/stdc++.h>
using namespace std;
const int maxn=65;
int main_worth[maxn],main_toval[maxn];
int annex_worth[maxn][3],annex_toval[maxn][3];
int n,m;
int x,y,z;
int ans[maxn*maxn*maxn*maxn];
inline void read(){
scanf("%d %d",&n,&m);
for (int i=1;i<=m;i++){
scanf("%d %d %d",&x,&y,&z);
if (!z)
{
main_worth[i]=x;
main_toval[i]=x*y;
}
else
{
annex_worth[z][0]++;
annex_worth[z][annex_worth[z][0]]=x;
annex_toval[z][annex_worth[z][0]]=x*y;
}
}
}
int main (){
read();
else
{
for (int i=1;i<=m;i++)
{
for (int j=n;j>=main_worth[i];j--)
{
ans[j]=max(ans[j],ans[j-main_worth[i]]+main_toval[i]);
if(j>main_worth[i]+annex_worth[i][1])
ans[j]=max(ans[j],ans[j-main_worth[i]-annex_worth[i][1]]+annex_toval[i][1]+main_toval[i]);
//main plus annex1 or not
if(j>main_worth[i]+annex_worth[i][2])
ans[j]=max(ans[j],ans[j-main_worth[i]-annex_worth[i][2]]+annex_toval[i][2]+main_toval[i]);
//main plus annex2 or not
if(j>main_worth[i]+annex_worth[i][1]+annex_worth[i][2])
ans[j]=max(ans[j],ans[j-main_worth[i]-annex_worth[i][1]-annex_worth[i][2]]+annex_toval[i][1]+annex_toval[i][2]+main_toval[i]);
//main plus annex1 and annex2 or not
}
}
cout<<ans[n];
}
return 0;
}
by 梁丘封冽 @ 2018-10-03 12:30:12
这是要干嘛