大逃杀
题目背景：
10.26 NOIP模拟T3
分析：树型DP
老子有句XXX真的非常想讲······我特喵的，喵了个咪的，喵喵喵喵喵！
好了发泄完了，准备说说怎么做，当时拿到这道题，第一发只想到了一个O(n4)的DP，我们定义状态f[i][j][0/1]表示，在以i为根的子树中，花费j的时间，0：从i出发最终回到i的最大获利，1：从i出发最终不回到i的最大获利，然后转移比较好想了
f[i][j][0] = max(f[i][j - 1][0], f[i][k][0] + f[i][j - k - 2 * dis][0])[v表示当前枚举到的儿子，dis表示v与i之间连边的消耗值，转移表示在之前枚举到的子树中走k个时间，最后回到i，然后走到v在v子树中走j - k - 2 * dis的时间然后，回到i的最大获利]
f[i][j][1] = max(f[i][j - 1][1], f[i][k][0] + f[v][j - k - dis][1]) [v和dis的意义同上，这个转移表示在之前的子树中，走k时间回到i，然后走到v，然后在v当中走j - k - dis的时间，不回到v，i的最大获利]
f[i][j][1] = max(f[[i][j][1], f[i][k][1] + f[v][j - k - 2 * dis][0])[v和dis意义同上，这个转移表示先从i走到v，在v的子树中走j - k - 2 * dis时间然后回到v，之后走到i，然后在之前的子树中走k时间，不回到i的最大获利]
显然这样只能针对一个点求出T秒的最大值·····以一个点为根，DP一次的复杂度是O(nT2)的，那么n次就是O(n2T2)最后得到了65分······
现在来说标算，其实标算想法很简单，我们在原来的DP基础上，再加上一种状态就好了，定义f[i][j][0/1/2]，0/1状态的转移和表示同之前的DP是一样的，而f[i][j][2]表示，从i的子树中出发，最终回到i的子树内部，（起点和终点都不是i，但是会经过i），考虑如何转移这个状态。
f[i][j][2] = max(f[i][j][2], f[i][k][1] + f[v][j - k - dis][1]) [v和dis的意义依然同上，这个转移的意思就是，从i之前的子树中的一个节点花费k时间来到i，然后在从i到v，然后在v子树中走j - k - dis的时间，最终不回到i的最大获利]
f[i][j][2] = max(f[i][j][2], f[i][k][0] + f[v][j - k - dis * 2][2]) [v和dis的意义同上，转移的意思为，从之前v子树中的一个节点走到v，然后走到i再在i之前的子树中走k个时间回到i，之后再走到v的子树中，最后不回到i的最大获利，这样说可能不清楚，请看下面这张图]
对应颜色的s,t表示对应路径的走法，红色的线表示的f[i][k][0]的走法，橙色的线表示的是f[v][j - k - dis * 2][2]的走法，绿色的线是两者合并的走法，所以需要减去2 * dis的时间。
f[i][j][2] = max(f[i][j][2], f[i][k][2] + f[v][j - k - 2 * dis][0]) [v,dis意义同上，这个表示从i原来的子树中的一个点出发来到i，然后从i到v在v的子树中走j - k - 2 * dis的时间，然后回到v，然后再走到i，最后走到i的子树当中的最大获利，图像同样在下方]
红色表示f[i][k][2], 橙色表示f[v][j - k - 2 *dis][0], 绿色表示两者合并。同样要减去2 * dis的时间
好了，至此2转移完成，然后我们的最终答案就是所有的f[i][T][0/1/2]的最大值·····复杂度O(n3)
注意：
1、显然我们在更新f[i][j][0/1/2]的时候，有调用过f[i][k][0/1/2]，那么如果想要不开辅助数组，那么一定就需要倒序枚举j才行
2、因为原题数据存在一些很奇妙的情况，比如dis可以为0·····那么就可能出现，我们在倒序更新的时候会用自己更新自己，比如用f[i][j][0]更新f[i][j][2]，用f[i][j][2]更新f[i][j][2]，那么就涉及到一些问题，为了不让转移混乱掉，我们要做到以下几点，第一更新顺序为先更新2，再更新1，再更新0，因为2状态由0, 1, 2状态更新，1状态由0,1状态更新，0状态由0状态更新，如果先更新了0，那么可能就会出现用新更新过的0状态更新了这一次的2状态，所以顺序为2,1,0，然后第二点就是，在用不同状态更新相同状态的过程中，又有顺序，要先用自己更新自己才行，比如你先用0状态更新了2状态，那么如果你要用2状态更新2状态时，就可能用新的2状态，更新了自己本身，又会出错······所以综合下来就是说，枚举j需要倒序枚举，枚举k要倒序枚举（先用自己更新自己），然后每一次更新先用2更新2，再用0,1更新2，再用1更新1，再用0更新1，最后用0更新0······总之被坑了好久好久····
65分DP
Source：
/*
created by scarlyw
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <ctime>
inline char read() {
static const int IN_LEN = 1024 * 1024;
static char buf[IN_LEN], *s, *t;
if (s == t) {
t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
if (s == t) return -1;
}
return *s++;
}
///*
template<class T>
inline void R(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = read(); !isdigit(c); c = read()) {
if (c == -1) return ;
if (c == '-') iosig = true;
}
for (x = 0; isdigit(c); c = read()) x = ((x << 2) + x << 1) + (c ^ '0');
if (iosig) x = -x;
}
//*/
const int OUT_LEN = 1024 * 1024;
char obuf[OUT_LEN], *oh = obuf;
inline void write_char(char c) {
if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
*oh++ = c;
}
template<class T>
inline void W(T x) {
static int buf[30], cnt;
if (x == 0) write_char('0');
else {
if (x < 0) write_char('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) write_char(buf[cnt--]);
}
}
inline void flush() {
fwrite(obuf, 1, oh - obuf, stdout);
}
/*
template<class T>
inline void R(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = getchar(); !isdigit(c); c = getchar()) {
if (c == -1) return ;
if (c == '-') iosig = true;
}
for (x = 0; isdigit(c); c = getchar()) x = ((x << 2) + x << 1) + (c ^ '0');
if (iosig) x = -x;
}
//*/
const int MAXN = 300 + 10;
struct node {
int to, w;
node(int to = 0, int w = 0) : to(to), w(w) {}
} ;
std::vector<node> edge[MAXN];
inline void add_edge(int x, int y, int z) {
edge[x].push_back(node(y, z)), edge[y].push_back(node(x, z));
}
int n, x, y, z, tot;
int w[MAXN], t[MAXN], f[MAXN][MAXN][2];
inline void read_in() {
R(n), R(tot);
for (int i = 1; i <= n; ++i) R(w[i]);
for (int i = 1; i <= n; ++i) R(t[i]);
for (int i = 1; i < n; ++i) R(x), R(y), R(z), add_edge(x, y, z);
}
inline void dfs1(int cur, int fa, int tt) {
for (int i = 0; i <= tt; ++i) f[cur][i][0] = f[cur][i][1] = 0;
int temp = tt - t[cur];
if (temp < 0) return ;
for (int p = 0; p < edge[cur].size(); ++p) {
node *e = &edge[cur][p];
if (e->to != fa) {
dfs1(e->to, cur, temp - e->w);
for (int i = temp; i > 0; --i) {
f[cur][i][0] = std::max(f[cur][i - 1][0], f[cur][i][0]);
f[cur][i][1] = std::max(f[cur][i - 1][1], f[cur][i][1]);
for (int j = e->w; j <= i; ++j) {
if (j >= 2 * e->w) {
f[cur][i][0] = std::max(f[cur][i][0],
f[cur][i - j][0] + f[e->to][j - 2 * e->w][0]);
f[cur][i][1] = std::max(f[cur][i][1],
f[cur][i - j][1] + f[e->to][j - 2 * e->w][0]);
}
if (j >= e->w) {
f[cur][i][1] = std::max(f[cur][i][1],
f[cur][i - j][0] + f[e->to][j - e->w][1]);
}
}
}
}
}
for (int i = tt; i >= t[cur]; --i) {
f[cur][i][0] = f[cur][i - t[cur]][0] + w[cur];
f[cur][i][1] = f[cur][i - t[cur]][1] + w[cur];
}
for (int i = 0; i < t[cur]; ++i) f[cur][i][0] = f[cur][i][1] = 0;
}
inline void solve() {
int ans = 0;
for (int i = 1; i <= n; ++i) {
dfs1(i, 0, tot);
ans = std::max(std::max(f[i][tot][0], f[i][tot][1]), ans);
}
std::cout << ans;
}
int main() {
// freopen("toyuq.in", "r", stdin);
// freopen("toyuq.out", "w", stdout);
read_in();
solve();
return 0;
}
100分DP
Source
/*
created by scarlyw
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <ctime>
inline char read() {
static const int IN_LEN = 1024 * 1024;
static char buf[IN_LEN], *s, *t;
if (s == t) {
t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
if (s == t) return -1;
}
return *s++;
}
///*
template<class T>
inline void R(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = read(); !isdigit(c); c = read()) {
if (c == -1) return ;
if (c == '-') iosig = true;
}
for (x = 0; isdigit(c); c = read()) x = ((x << 2) + x << 1) + (c ^ '0');
if (iosig) x = -x;
}
//*/
const int OUT_LEN = 1024 * 1024;
char obuf[OUT_LEN], *oh = obuf;
inline void write_char(char c) {
if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
*oh++ = c;
}
template<class T>
inline void W(T x) {
static int buf[30], cnt;
if (x == 0) write_char('0');
else {
if (x < 0) write_char('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) write_char(buf[cnt--]);
}
}
inline void flush() {
fwrite(obuf, 1, oh - obuf, stdout);
}
/*
template<class T>
inline void R(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = getchar(); !isdigit(c); c = getchar()) {
if (c == -1) return ;
if (c == '-') iosig = true;
}
for (x = 0; isdigit(c); c = getchar()) x = ((x << 2) + x << 1) + (c ^ '0');
if (iosig) x = -x;
}
//*/
const int MAXN = 300 + 10;
struct node {
int to, w;
node(int to = 0, int w = 0) : to(to), w(w) {}
} ;
std::vector<node> edge[MAXN];
inline void add_edge(int x, int y, int z) {
edge[x].push_back(node(y, z)), edge[y].push_back(node(x, z));
}
int n, x, y, z, tot;
int w[MAXN], t[MAXN], f[MAXN][MAXN][3];
inline void read_in() {
R(n), R(tot);
for (int i = 1; i <= n; ++i) R(w[i]);
for (int i = 1; i <= n; ++i) R(t[i]);
for (int i = 1; i < n; ++i) R(x), R(y), R(z), add_edge(x, y, z);
}
inline void dfs1(int cur, int fa) {
for (int i = t[cur]; i <= tot; ++i)
f[cur][i][0] = f[cur][i][1] = f[cur][i][2] = w[cur];
for (int p = 0; p < edge[cur].size(); ++p) {
node *e = &edge[cur][p];
if (e->to != fa) {
dfs1(e->to, cur);
for (int i = tot; i >= 0; --i) {
for (int j = i - 2 * e->w; j >= t[cur]; --j) {
f[cur][i][2] = std::max(f[cur][i][2],
f[cur][j][2] + f[e->to][i - j - 2 * e->w][0]);
f[cur][i][2] = std::max(f[cur][i][2],
f[cur][j][0] + f[e->to][i - j - 2 * e->w][2]);
}
for (int j = i - e->w; j >= t[cur]; --j) {
f[cur][i][2] = std::max(f[cur][i][2],
f[cur][j][1] + f[e->to][i - j - e->w][1]);
}
for (int j = i - 2 * e->w; j >= t[cur]; --j) {
f[cur][i][1] = std::max(f[cur][i][1],
f[cur][j][1] + f[e->to][i - j - 2 * e->w][0]);
}
for (int j = i - e->w; j >= t[cur]; --j) {
f[cur][i][1] = std::max(f[cur][i][1],
f[cur][j][0] + f[e->to][i - j - e->w][1]);
}
for (int j = i - 2 * e->w; j >= t[cur]; --j) {
f[cur][i][0] = std::max(f[cur][i][0],
f[cur][j][0] + f[e->to][i - j - 2 * e->w][0]);
}
}
}
}
}
inline void solve() {
int ans = 0;
dfs1(1, 0);
for (int i = 1; i <= n; ++i)
ans = std::max(std::max(f[i][tot][0], f[i][tot][1]),
std::max(ans, f[i][tot][2]));
std::cout << ans;
}
int main() {
// freopen("toyuq.in", "r", stdin);
// freopen("toyuq.out", "w", stdout);
read_in();
solve();
return 0;
}