题目

Description

今天Karen要去买东西。

一共有 \(n\) 件物品,每件物品的价格为\(c_i\),同时每件物品都有一张优惠券,可以对这件物品减价 \(d_i\) . 使用第 \(i\) 件物品的优惠券的条件是买这件物品并且使用了第 \(x_i\) 张优惠券。现在给出Karen带的钱数 \(b\) ,问最多能买几件物品。

Input

第一行两个整数 \(n\le 5\times 10^3 , b\le 10^9\) 。

接下来 \(n\) 行中第 \(i\) 行,首先有两个整数 \(c_i,d_i\le 10^9\) 。对于 \(i>1\) 有第三个整数 \(1\le x_i<i\) 。

Output

一行,输出最多能买的物品个数。

Sample Input

样例1:

6 16

10 9

10 5 1

12 2 1

20 18 3

10 2 3

2 1 5

样例2:

5 10

3 1

3 1 1

3 1 2

3 1 3

3 1 4

Sample Output

样例1:

4

样例2:

5

Hint

样例1: 买1,3,4号物品,用优惠券;买6号物品,不用优惠券

样例2:买所有的的物品,用优惠券

分析

由于每个物品只有一件,我们可以把问题转化成求买 \(k\) 个物品至少需要多少钱,最后再统计最多可以买多少个。

由于有 \(1\le x_i<i\) ,所以优惠券的使用条件构成了一棵树。现在问题是如何在这颗树上求解。

注意到如果一个点不用优惠券,那么子树中所有点都不能用,所以设状态:

\(f[x][i][0,1]\) 表示以 \(x\) 为根的子树中买 \(i\) 件物品,是否可以用优惠券(0不能,1能),那么可以通过子树的信息来更新当前点:

\[f[x][i+j][0]=\min \{f[u][i][0]+f[v][j][0],u,v\in \text{subtree}(x)\} \\
f[x][i+j][1]=\min \{f[u][i][1]+f[v][j][1],f[u][i][0]+f[v][j][1],u,v\in \text{subtree}(x)\} \\
\]

即如果当前点不可用优惠券,那么子树都不能用。如果当前点用优惠券,那么子树可用可不用。

这样\(f[\text{root}][k][1]\)就是我们要求的东西。

这样做似乎是\(O(n^3)\)的呢!我们实际上是枚举子树中的点对,所以可以不断地把点合并进当前点中,就可以做到\(n^2\)级别了。

循环的时候要从后往前,否则无法保证每件物品只买一次。

代码

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long giant;
int read() {
int x=0,f=1;
char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int maxn=5e3+10;
const giant inf=1e13;
int n,bud;
giant f[maxn][maxn][2];
vector<int> g[maxn];
void add(int x,int y) {g[x].push_back(y);}
void Min(giant &x,giant y) {x=min(x,y);}
int dfs(int x) {
int sz=1;
for (int v:g[x]) {
int vs=dfs(v);
for (int j=sz;j>=0;--j) {
for (int i=vs;i>=0;--i) {
Min(f[x][i+j][0],f[x][j][0]+f[v][i][0]);
Min(f[x][i+j][1],f[x][j][1]+f[v][i][1]);
}
}
sz+=vs;
}
for (int i=0;i<=n;++i) Min(f[x][i][1],f[x][i][0]);
return sz;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
n=read(),bud=read();
for (int i=1;i<=n;++i) for (int j=0;j<=n;++j) for (int k=0;k<2;++k) f[i][j][k]=inf;
for (int i=1;i<=n;++i) {
f[i][0][0]=0,f[i][1][0]=read(),f[i][1][1]=f[i][1][0]-read();
if (i>1) add(read(),i);
}
dfs(1);
int ans=0;
for (int i=1;i<=n;++i) if (f[1][i][1]<=bud) ans=i;
printf("%d\n",ans);
return 0;
}

最新文章

  1. Linux学习笔记之兄弟连
  2. IOS中的多线程之GCD
  3. pg_dump 备份与恢复的简单操作
  4. iOS 基础 第一天(0804)
  5. How to use BMW Multi Tool 7.3 to replace lost key for BMW X1
  6. .NET MVC4 实训记录之四(Unit of work + Repository)
  7. javascript Function.prototype.bind
  8. 浅析Content Negotation在Nancy的实现和使用
  9. cookie和session的区别异同
  10. 【margin和padding的区别】
  11. win10 1803版本unable to start ssh-agent service, error :1058
  12. C语言volatile关键字-漫画(转)
  13. Eureka控制台参数说明
  14. pika的阻塞式使用
  15. P3804 【模板】后缀自动机
  16. 菜鸟调错(一)——Maven项目部署到Jboss出现:Failed to create a new SAX parser
  17. CVE-2011-0104 Microsoft Office Excel缓冲区溢出漏洞 分析
  18. freemarker${}包含${}
  19. collides with another import statement解决办法
  20. POJ 2886.Who Gets the Most Candies? -线段树(单点更新、类约瑟夫问题)

热门文章

  1. 20155316 2016-2017-2 《Java程序设计》第9周学习总结
  2. 20155320 2016-2017-2《Java程序设计》第九周学习总结
  3. C语言复习20170805
  4. 微信小程序解决地图上的层级关系
  5. echarts 柱状图移除圆角
  6. 【转载】OGRE 2.1 Windows 编译
  7. 【LG4309】【BZOJ3173】[TJOI2013]最长上升子序列
  8. python基础&mdash;&mdash;字符串
  9. 解决WCF传输的数据量过大问题
  10. vue异步分页+初始化页面