Codeforces Round #419 (Div. 2) E. Karen and Supermarket(树形DP)

题目链接：Codeforces Round #419 (Div. 2) E. Karen and Supermarket

题意：

有n件物品，每个物品有一个价格，和一个使用优惠券的价格，不过这个优惠券有一个限制，必须要在第x个使用后才可以使用。现在有m的钱，问最多能买多少个物品。

题解：

每个优惠券都只与一个券有关，所以根据这个关系就可以构成一棵树。

考虑树形dp，dp[i][j][k(0|1)]表示第i个节点所构成的子树中买了j个物品，使用优惠券和不使用优惠券的最少钱。

转移方程看代码详细解释。

三个for看起来像n³不过实际只有n²。

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 #define ___ freopen("c:\code\in.txt","r",stdin);
 4 using namespace std;
 5 typedef long long ll;
 6 typedef pair<int,int>P;
 7 
 8 const int N=5007;
 9 
10 int n,m,sz[N];
11 P a[N];
12 ll dp[N][N][2],inf=1ll<<61;
13 vector<int>g[N];
14 
15 void up(ll &a,ll b){if(a>b)a=b;}
16 
17 void dfs(int x=1)
18 {
19     sz[x]=1,dp[x][0][0]=0;
20     dp[x][1][0]=a[x].first;
21     dp[x][1][1]=a[x].first-a[x].second;
22     for(auto &it:g[x])
23     {
24         dfs(it);
25         for(int i=sz[x];i>=0;i--)F(j,0,sz[it])
26         {
27             up(dp[x][i+j][0],dp[it][j][0]+dp[x][i][0]);//i+j不使用券 j和i必然不能使用券
28             up(dp[x][i+j][1],dp[it][j][0]+dp[x][i][1]);//i+j使用券 j不使用券 i必须使用券
29             up(dp[x][i+j][1],dp[it][j][1]+dp[x][i][1]);//i+j使用券 j使用券 i必须使用券
30         }
31         sz[x]+=sz[it];
32     }
33 }
34 
35 int main(){
36     scanf("%d%d",&n,&m);
37     scanf("%d%d",&a[1].first,&a[1].second);
38     F(i,2,n)
39     {
40         int x,y,z;
41         scanf("%d%d%d",&x,&y,&z);
42         a[i]=P(x,y),g[z].push_back(i);
43     }
44     F(i,0,n)F(j,0,n)dp[i][j][0]=dp[i][j][1]=inf;
45     dfs();
46     int ans=0;
47     for(int i=n;i>=0;i--)
48         if(dp[1][i][0]<=m||dp[1][i][1]<=m){ans=i;break;}
49     printf("%d
",ans);
50     return 0;
51 }

View Code