过了,但有个地方不知道为什么对

P1064 [NOIP2006 提高组] 金明的预算方案

_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;
}

|