ygsldr @ 2017-07-10 09:17:24
如题
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstring>
#include <map>
#include <cstdlib>
#include <queue>
using namespace std;
int max(int a, int b);
int min(int a, int b);
int read();
void write(int x);
struct obj
{
int toward1, toward2;//指向两个附件
int cost, imp, mostcost;//单件消耗,单件重要程度,连带附件消耗
bool dododo;//是否为附件
}a[60];
int dp[40000];
int main()
{
int m(read()), n(read()), tmp1, tmp2, tmp3;
for (int i(1); i <= n; ++i)
{
a[i].toward1 = 0;
a[i].toward2 = 0;
a[i].mostcost = 0;
a[i].dododo = true;
}//初始化
for (int i(1); i <= n; ++i)
{
tmp1 = read();//价格
tmp2 = read();//重要度
tmp3 = read();//附件
tmp2 *= tmp1;//相乘为val
a[i].cost = tmp1;//记录消耗的钱
a[i].imp = tmp2;//记录val
if (tmp3 == 0)
{
a[i].mostcost += a[i].cost;//如果为主件,累加最大值
continue;
}
else
{
a[tmp3].mostcost += a[i].cost;//如果为附件,将消耗累加到他的主件上
a[i].dododo = false;//该件不能单独取
if (a[tmp3].toward1 == 0)a[tmp3].toward1 = i;
else a[tmp3].toward2 = i;//记录此附件的位置
}
}
for (int i(1); i <= n; ++i)
{
if (a[i].dododo == false)continue;//跳过附件
for (int j(m); j >= a[i].mostcost; --j)
{
dp[j] = max(dp[j], dp[j - a[i].cost] + a[i].imp);//只取A
if (a[i].toward1)
{
dp[j] = max(dp[j], dp[j - a[i].cost - a[a[i].toward1].cost] + a[i].imp + a[a[i].toward1].imp);//取A,B
}
if (a[i].toward2)
{
dp[j] = max(dp[j], dp[j - a[i].cost - a[a[i].toward2].cost] + a[i].imp + a[a[i].toward2].imp);//取A,C;A,B,C
dp[j] = max(dp[j], dp[j - a[i].cost - a[a[i].toward1].cost - a[a[i].toward2].cost] + a[i].imp + a[a[i].toward1].imp + a[a[i].toward2].imp);
}
}
}
write(dp[m]);//输出
return 0;
}
inline int max(int a, int b)
{
return a > b ? a : b;
}
inline int min(int a, int b)
{
return a < b ? a : b;
}
inline int read()
{
int x(0), f(1);
char ch = getchar();
while (ch > '9' || ch < '0')
{
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline void write(int x)
{
if (x == 0)
{
putchar('0');
return;
}
if (x < 0)
{
putchar('-');
x = -x;
}
char ch[20];
int num(0);
while (x > 0)
{
ch[num] = x % 10 + '0';
x /= 10;
++num;
}
for (int i(num - 1); i >= 0; --i)putchar(ch[i]);
return;
}