abjfj @ 2019-09-16 21:59:44
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int v,p,q;
}a[1001];
int n,m;
int f[32001];
int save[61][61];
int cnt1[61];//记录组的件数
int cnt2[61];//记录不同附件的种类
int v[61][61];
int c[61][61];
int main()
{
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
cin>>a[i].v>>a[i].p>>a[i].q;
a[i].p*=a[i].v;
if(a[i].q > 0)
{
cnt1[a[i].q]++;
save[a[i].q][cnt1[a[i].q]] = i;
}
}
/*for(int i = 1; i <= m; i++)
{
if(!a[i].q)
{
cout<<"主件:"<<i<<":"<<endl;
for(int j = 1; j <= cnt1[i]; j++)
{
int y = save[i][j];
cout<<y<<endl;
}
}
}*/
for(int i = 1; i <= m; i++)
{
if(!a[i].q)
{
memset(f,-1,sizeof(f));
f[0] = 0;
for(int j = 1; j <= cnt1[i]; j++)
{
int y = save[i][j];
// cout<< a[y].v+a[i].v<<endl;
for(int k = n; k >= a[y].v+a[i].v; k--)
{
if(f[k-a[y].v-a[i].v]!=-1)
f[k] = max(f[k],f[k-a[y].v-a[i].v] + a[y].p + a[i].p);
/*
这样写转移时会计算两次主件。
所以错了。
*/
}
}
for(int j = 1; j <= n; j++)
{
if(f[j] != -1)
{
//cout<<1<<endl;
cnt2[i]++;
v[i][cnt2[i]] = j;
c[i][cnt2[i]] = f[j];
}
}
cnt2[i]++;
v[i][cnt2[i]] = a[i].v;
c[i][cnt2[i]] = a[i].p;
}
}
memset(f,0,sizeof(f));
for(int i = 1; i <= m; i++)
{
if(!a[i].q)
{
// cout<<"主件:"<<i<<":"<<endl;
for(int k = n; k >= 0; k--)
for(int j = 1; j <= cnt2[i]; j++)
{
//cout<<v[i][j]<<" "<<c[i][j]<<endl;
if(k-v[i][j] >= 0)
{
f[k] = max(f[k],f[k-v[i][j]] + c[i][j]);
}
}
}
}
int ans = 0;
for(int i = 0; i <= n; i++)ans = max(ans,f[n]);
cout<<ans<<endl;
return 0;
}
by 3f3f49wqn1 @ 2020-02-09 17:59:20
谢谢大佬