本文主要是介绍Codeforces Round #419 (Div. 1) C. Karen and Supermarket（树上背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/contest/815/problem/C
啊，怎么xjb剪剪枝就过了啊，最开始写了个一个5000^3的算法，然后就T了啊。。。。后来约束了一下背包的上界，就过了？题解说复杂度变成了O(n^2)，考虑一下满二叉树，我感觉我这样是带着log的啊？竟然分析不出来复杂度了。。。
剩下的就是一个裸的树上背包了啊？敢写敢过？
dp[now][x][1]表示，在now节点，买x个，并且now可以使用优惠券的最小花费
dp[now][x][0]表示，在now节点，买x个，并且now不可以使用优惠券的最小花费
然后XJB转移就好了2333333
反正复杂度O(能过)
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
const int INF=0x3f3f3f3f;
int dp[MAXN][MAXN][2];
int c[MAXN],d[MAXN],mx[MAXN];
vector<int> E[MAXN];
int tmp[MAXN][2];
void dfssize(int now)
{mx[now]=1;for(int _=0;_<E[now].size();_++){int v=E[now][_];dfssize(v);mx[now]+=mx[v];}
}
void dfs(int now)
{int M=1,sz=1;dp[now][0][0]=0;dp[now][1][0]=c[now];dp[now][1][1]=c[now]-d[now];for(int _=0;_<E[now].size();_++){int v=E[now][_];dfs(v);for(int i=0;i<=mx[now];i++){tmp[i][0]=dp[now][i][0];tmp[i][1]=dp[now][i][1];}for(int i=mx[v];i>=0;i--){for(int j=min(sz,mx[now]);j>=0;j--){if(dp[now][j][0]!=INF){tmp[j+i][0]=min(tmp[j+i][0],dp[now][j][0]+dp[v][i][0]);M=max(M,j+i);}if(dp[now][j][1]!=INF){tmp[j+i][1]=min(tmp[j+i][1],dp[now][j][1]+dp[v][i][0]);tmp[j+i][1]=min(tmp[j+i][1],dp[now][j][1]+dp[v][i][1]);M=max(M,j+i);}}}sz=max(M,sz);for(int i=min(sz,mx[now]);i>=0;i--){if(tmp[i][0]!=INF)dp[now][i][0]=min(dp[now][i][0],tmp[i][0]);if(tmp[i][1]!=INF)dp[now][i][1]=min(dp[now][i][1],tmp[i][1]);}}
}
int n,b;
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);memset(dp,0x3f,sizeof(dp));scanf("%d%d",&n,&b);for(int i=1;i<=n;i++){scanf("%d%d",&c[i],&d[i]);if(i!=1){int u;scanf("%d",&u);E[u].push_back(i);}}dfssize(1);dfs(1);int ans=0;for(int i=1;i<=n;i++){if(dp[1][i][1]<=b||dp[1][i][0]<=b)ans=i;}printf("%d\n",ans);return 0;
}这篇关于Codeforces Round #419 (Div. 1) C. Karen and Supermarket（树上背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
