_visionary @ 2023-12-05 23:43:56
下面的代码,我不是很理解为什么k循环中forup (k, item[v].cost, min(sz[v], j - item[u].cost))要j - item[u].cost才能过,j 就不行,我理解上不应该是 j 才对吗。上一次递归时不是把item[u].cost给去掉了吗,为什么再去一次,求大佬解答orz
#include <bits/stdc++.h>
#define forup(i, l, r) for(int i = l; i <= r; i++)
#define fordown(i, l, r) for(int i = r; i >= l; i--)
using namespace std;
struct Item
{
int cost, value;
vector<int> post;
} item[100];
int money, num;
int dp[100][32005];
int sz[100];
void Dfs(int u, int restMoney)
{
sz[u] = item[u].cost;
forup (i, item[u].cost, money) dp[u][i] = item[u].cost * item[u].value;
for (int v: item[u].post)
{
Dfs(v, restMoney - item[v].cost);
sz[u] += sz[v];
fordown (j, item[v].cost, restMoney)
{
forup (k, item[v].cost, min(sz[v], j - item[u].cost))
{
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
}
}
}
}
int main()
{
cin>>money>>num;
money /= 10;
forup (i, 1, num)
{
cin>>item[i].cost>>item[i].value;
item[i].cost /= 10;
int pre; cin>>pre;
item[pre].post.push_back(i);
}
Dfs(0, money);
int ans = 0;
forup (i, 0, money) ans = max(ans, dp[0][i]);
cout<<ans * 10;
return 0;
}