正确代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<climits>
#include<cctype>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<string.h>
using namespace std;
#pragma warning(disable:4996)
#define mx(a,b) (a>b?a:b)
#define mn(a,b) (a<b?a:b)
#define sfd(x) scanf("%d",&x)
#define sflf(x) scanf("%lf", &x)
#define pfd(x) printf("%d",x)
#define ini(x,y) memset(x,y,sizeof(x))
const int maxn = 3005, maxm = 3005;
struct Edge
{int v, w;
};
Edge edg[maxm];
int h[maxn], nxt[maxm], dp[maxn][maxn], n, m;
int esize = 0;
inline void add(int u, int v, int w)
{esize++;edg[esize] = { v,w };nxt[esize] = h[u];h[u] = esize;
}
int f(int u)
{if (u >= n - m + 1){return 1;}int sum = 0;for (int i = h[u]; i; i = nxt[i]){int v = edg[i].v;int t = f(v);sum += t;for (int j = m; j; j--){for (int k = min(t,j); k; k--){dp[u][j] = mx(dp[u][j], dp[u][j - k] - edg[i].w + dp[v][k]);}}}return sum;
}
int main()
{ini(h,0);fill(dp[0],dp[0]+maxn*maxn,INT_MIN/2);sfd(n), sfd(m);for (int i = 1; i <= n - m; i++){int k; sfd(k);while (k--){int v, w; sfd(v), sfd(w);add(i, v, w);}}for (int i = 1; i <= n; i++){dp[i][0] = 0;}for (int i = n - m + 1; i <= n; i++){sfd(dp[i][1]);}int t=f(1);for (int i = t; i>=0; i--){if (dp[1][i]>=0){pfd(i);break;}}
}
错误代码
int f(int u)
{if (u >= n - m + 1){return 1;}int sum = 0;for (int i = h[u]; i; i = nxt[i]){int v = edg[i].v;int t = f(v);sum += t;for (int j = 1; j <= t; j++){for (int k = m; k; k--){dp[u][k] = mx(dp[u][k], dp[u][k -j] - edg[i].w + dp[v][j]);}}}return sum;
}
和01背包不同，dp[u][x]的没一个值都需要独立计算，因为我们是期望算出子树中所有可能的结果，对于一个子树，不能在已经满足x个客户的基础上，计算满足客户x+1个客户的最大盈利，这样很有可能是冲突的。