dinghongyu @ 2019-01-29 12:21:08
#include <bits/stdc++.h>
using namespace std;
int n,m,f[32001];
int v1,p1,q1;
struct _
{
int v,w,q; //v,价值;w,乘积
int num,fj[3][3]; //num,附件数;fj,附件信息:fj[i][1],价值;fj[i][2],乘积
}a[61];
bool b[61];
int main()
{
cin >> n >> m;
for (int i = 1;i <= m;i++)
{
cin >> v1 >> p1 >> q1;
if (!q1) //主件
a[i].v = v1,a[i].w = v1 * p1;
else //附件
a[q1].num++,a[q1].fj[a[q1].num][1] = v1,a[q1].fj[a[q1].num][2] = v1 * p1,b[i] = 1;
}
for (int i = 1;i <= m;i++)
{
for (int j = n;j >= a[i].v;j--)
{
if (b[i])
continue; //是附件
f[j] = max(f[j],f[j - a[i].v] + a[i].w);//仅购主件
if (a[i].num)
{
if (j >= a[i].v + a[i].fj[1][1] + a[i].fj[2][1])
f[j] = max(f[j],f[j - a[i].v - a[i].fj[1][1] - a[i].fj[2][1]] + a[i].w + a[i].fj[1][2] + a[i].fj[2][2]);//购买主件,附件1和附件2
if (j >= a[i].v + a[i].fj[1][1])
f[j] = max(f[j],f[j - a[i].v - a[i].fj[1][1]] + a[i].v + a[i].fj[1][2]);//购买主件+附件1
if (j >= a[i].v + a[i].fj[2][1])
f[j] = max(f[j],f[j - a[i].v - a[i].fj[2][1]] + a[i].v + a[i].fj[2][2]);//购买主件+附件2
}
}
}
cout << f[n];
return 0;
}
by dinghongyu @ 2019-01-29 12:24:57
第三个点A不了。。。
by chenyanming @ 2019-01-29 12:30:27
如果不买呢
by dinghongyu @ 2019-01-29 12:43:49
不买就是等于
by dinghongyu @ 2019-01-29 12:43:55
@chenyanming