LINK

题意：给出n个商品，除第一个商品外，所有商品可以选择使用优惠券，但要求其前驱商品已被购买，问消费k以下能买几个不同的商品

思路：题意很明显就是树形DP。对于一个商品有三种选择，买且使用优惠券，买不使用优惠券，不买。当然如果直接暴力进行转移是$O(n^3)$的，但我们可以统计每个结点其子节点的个数sz，sz~0地来遍历，这样就可以将某节点与其父节点进行转移，从而避免了多余无效的转移，优化到$O(n^2)$。dp[k][i][j]代表 k是否不使用优惠券，以i为父节点 购买j个商品的最小花费。

/** @Date    : 2017-07-01 15:38:39  * @FileName: 816E 树形DP.cpp  * @Platform: Windows  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version : $Id$  */#include <bits/stdc++.h>#define LL long long#define PII pair#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const LL INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;LL n, m;LL c[N], b[N];LL dp[2][5010][5010];int sz[5010];vector edg[5010];int dfs(int x, int pre){	sz[x] = 1;	dp[1][x][0] = 0;	dp[1][x][1] = c[x];//不用优惠券	dp[0][x][1] = c[x] - b[x];//用优惠券	for(auto np:edg[x])	{		if(np == pre)			continue;		dfs(np, x);		for(int i = sz[x]; i >= 0; i--)//		{			for(int j = sz[np]; j >= 0; j--)			{				dp[0][x][i + j] = min(dp[0][x][i + j], dp[0][x][i] + min(dp[1][np][j], dp[0][np][j]));				dp[1][x][i + j] = min(dp[1][x][i + j], dp[1][x][i] + dp[1][np][j]);			}		}		sz[x] += sz[np];	}}int main(){	while(cin >> n >> m)	{		MMF(sz);		MMI(dp);		int t;		scanf("%lld%lld", c + 1, b + 1);		for(int i = 2; i <= n; i++)		{			scanf("%lld%lld%d", c + i, b + i, &t);			edg[t].PB(i);		}		dfs(1, -1);		for(int i = n; i >= 0; i--)		{			LL mi = min(dp[1][1][i], dp[0][1][i]);			if(mi <= m)			{				printf("%d\n", i);				break;			}		}	}    return 0;}

816E. Karen and Supermarket 树形DP