codeforces 816 E. Karen and Supermarket(树形dp)

时间:2022-04-06 11:41:47

题目链接:http://codeforces.com/contest/816/problem/E

题意:有n件商品,每件有价格ci,优惠券di,对于i>=2,使用di的条件为:xi的优惠券需要被使用,问初始金钱为b时 最多能买多少件商品? n<=5000,ci,di,b<=1e9

题解:显然是一道树形dp由于有两种情况就是当前点为根结点的时候选择打折还是不打折,如果选不打折之后的节点都不能打折。

不妨设dp[i][j][flag]表示i为根j为种类数,flag为状态表示选不选打折的最小花费。转移方程为

dp[u][j + l][0] = min(dp[u][j + l][0] , dp[u][j][0] + dp[v][l][0]);

dp[u][j + l][1] = min(dp[u][j + l][1] , min(dp[u][j][1] + dp[v][l][0] , dp[u][j][1] + dp[v][l][1]));

具体看代码。

#include <iostream>
#include <cstring>
#include <vector>
#define inf 0X3f3f3f3f
using namespace std;
typedef long long ll;
const int M = 5e3 + 10;
vector<int>vc[M];
ll pa[M] , pb[M] , dp[M][M][2] , sz[M];
void dfs(int u) {
int len = vc[u].size();
sz[u] = 1;
dp[u][0][0] = 0 , dp[u][1][0] = pa[u] , dp[u][1][1] = pa[u] - pb[u];
for(int i = 0 ; i < len ; i++) {
int v = vc[u][i];
dfs(v);
for(ll j = sz[u] ; j >= 0 ; j--) {
for(ll l = 0 ; l <= sz[v] ; l++) {
dp[u][j + l][0] = min(dp[u][j + l][0] , dp[u][j][0] + dp[v][l][0]);
dp[u][j + l][1] = min(dp[u][j + l][1] , min(dp[u][j][1] + dp[v][l][0] , dp[u][j][1] + dp[v][l][1]));
}
}
sz[u] += sz[v];
}//这里看似是3个for实际上就是3个for但是复杂度却不是O(n^3),由于sz[i]表示的是以i为根的最多有几个子节点类似前缀的一种东西,由于dfs,这些sz只会用一次不会有重复。所以理论上复杂度就是O(n^2)。
}
int main() {
int n , b;
scanf("%d%d" , &n , &b);
for(int i = 1 ; i <= n ; i++) {
int c , d , x;
if(i == 1) {
scanf("%d%d" , &c , &d);
pa[i] = c , pb[i] = d;
}
else {
scanf("%d%d%d" , &c , &d , &x);
pa[i] = c , pb[i] = d;
vc[x].push_back(i);
}
}
memset(dp , inf , sizeof(dp));
dfs(1);
int ans = 0;
for(int i = 0 ; i <= n ; i++) {
if(dp[1][i][0] <= b || dp[1][i][1] <= b) ans = i;
}
printf("%d\n" , ans);
return 0;
}