Codeforces1099F. Cookies【DP】【线段树】【贪心】【博弈】【沙比提(这是啥算法)】

LINK


题目大意

给你一棵树,每个节点上有一堆饼干

并且告诉你在每个节点上吃饼干吃一块需要多少时间

然后告诉你经过一条边的时间

总时间是T

两个人轮流进行,一个人向下选择子节点行走或者结束游戏并向上移动吃饼干,另一个人割断一条当前节点到儿子的边或者什么都不做

问第一个人可以吃到的最大的饼干的数量

思路

首先可以把边上的时间在dfs的时候抛掉

然后如果在一个节点上停了下来

我们考虑怎么统计吃的饼干,我们肯定会贪心选择需要时间最少的先吃,这样才能吃到尽量多块

然后用线段树(把单个时间当做下标)维护一下链上的所有信息

然后如果在这个节点不停下来,我们需要递归成子问题

显然第二个人会把往下走dp值最大的一个子树搞掉,所以当前的dp值就是往下走的第二大和停下来的max

在第一个节点特判一下就好了


#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N = 1e6 + 10; 

struct Node {
ll v, w;
} p[N];
vector<Node> g[N];
ll n, T; #define LD (t << 1)
#define RD (t << 1 | 1) ll val[N << 2], siz[N << 2]; void insert(ll t, ll l, ll r, ll pos, ll cursiz) {
val[t] += pos * cursiz;
siz[t] += cursiz;
if (l == r) return;
ll mid = (l + r) >> 1;
if (pos <= mid) insert(LD, l, mid, pos, cursiz);
else insert(RD, mid + 1, r, pos, cursiz);
} ll query(ll t, ll l, ll r, ll vl) {
if (l == r) return min(siz[t], vl / l);
ll mid = (l + r) >> 1;
if (val[LD] <= vl) return siz[LD] + query(RD, mid + 1, r, vl - val[LD]);
else return query(LD, l, mid, vl);
} ll dfs(ll u, ll lef) {
insert(1, 1, 1e6, p[u].w, p[u].v);
ll res = query(1, 1, 1e6, lef);
ll f1 = 0, f2 = 0;
for (auto now : g[u]) {
ll v = now.v;
if (lef <= now.w * 2) continue;
ll cur = dfs(v, lef - now.w * 2);
if (cur > f1) f2 = f1, f1 = cur;
else if (cur > f2) f2 = cur;
}
insert(1, 1, 1e6, p[u].w, -p[u].v);
if (u == 1) return max(res, f1);
else return max(res, f2);
} int main() {
scanf("%lld %lld", &n, &T);
for (ll i = 1; i <= n; i++) scanf("%lld", &p[i].v);
for (ll i = 1; i <= n; i++) scanf("%lld", &p[i].w);
for (ll i = 2; i <= n; i++) {
ll u, w; scanf("%lld %lld", &u, &w);
g[u].push_back((Node) {i, w});
}
printf("%lld", dfs(1, T));
return 0;
}
上一篇:iOS 将对象的属性和属性值拆分成key、value,通过字符串key来获取该属性的值


下一篇:Dubbo服务集群,常见容错机制:failover ,failsafe,failfase ,failback,forking