萌新刚学OI,40WA求助

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

_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 ???


|