_LX_ @ 2022-10-24 16:06:58
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Node
{
int pr, vl, anc;
} node[55];
vector<int> v[55];
int dp[3250], n, m, nw[3250], ans;
signed main()
{
scanf("%d%d", &n, &m);
n /= 10;
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &node[i].pr, &node[i].vl, &node[i].anc);
node[i].pr /= 10;
if (node[i].anc != 0)
v[node[i].anc].push_back(i);
}
for (int i = 1; i <= m; i++)
{
if (node[i].anc != 0)
continue;
for (int j = n; j >= node[i].pr; j--)
{
nw[j] = max(dp[j], dp[j - node[i].pr] + node[i].pr * node[i].vl);
}
if (v[i].size() >= 1)
{
for (int j = n; j >= node[i].pr + node[v[i][0]].pr; j--)
nw[j] = max(nw[j], dp[j - node[i].pr - node[v[i][0]].pr] + node[i].pr * node[i].vl + node[v[i][0]].pr * node[v[i][0]].vl);
}
if (v[i].size() == 2)
{
for (int j = n; j >= node[i].pr + node[v[i][1]].pr; j--)
nw[j] = max(nw[j], dp[i - node[i].pr - node[v[i][1]].pr] + node[i].pr * node[i].vl + node[v[i][1]].pr * node[v[i][1]].vl);
for (int j = n; j >= node[i].pr + node[v[i][0]].pr + node[v[i][1]].pr; j--)
nw[j] = max(nw[j], dp[i - node[i].pr - node[v[i][0]].pr - node[v[i][1]].pr] + node[i].pr * node[i].vl + node[v[i][0]].pr * node[v[i][0]].vl + node[v[i][1]].pr * node[v[i][1]].vl);
}
for (int i = 0; i <= n; i++)
dp[i] = nw[i];
}
printf("%d\n", dp[n] * 10);
return 0;
}
码风清奇,请诸位神犇努力理解
值得注意的是,C++14(GCC9) 30WA , C++14(GCC9)O2 20WA , C++14O2 40WA
by x232 @ 2022-10-27 19:48:56
TIP:这个人提高冲一等
by _LX_ @ 2022-10-28 09:51:37
@hanyuchen2010 ???