树形 DP 练手题。。
题目传送门
大体思路
一句话：直接把结构存到树里，进行树形 DP。
存树
输入：\(w_1, w_2\)
-
如果是叶子节点（\(w_2 > 0\)）：
-
\(w_{cur} = w_1 * 2\)
-
\(val_{cur} = w_2\)
-
-
如果是内部节点（\(w_2 = 0\)）：
-
递归构建左子树
-
递归构建右子树
-
具体实现：
build
int build() {int w1, w2, cur = ++tot;cin >> w1 >> w2;w[cur] = w1 * 2;if (w2)val[cur] = w2;else {int l = build();G[cur].push_back(l);int r = build();G[cur].push_back(r);}return cur;//你反不返回都行，这样也能过
}
DP
这里可能要进行一个树上的分组背包了。
初始化
siz[cur] = val[cur] * 5 + w[cur];//初始化偷光所有画的时间
dp[cur][i] = min((i - w[cur]) / 5, val[cur]);//i 时间能偷的画数
树上分组背包
怎么背？板子怎么背就怎么背。
背
int p = min(t - 1, w[cur]);dp[cur][0] = dp[cur][p] = 0;siz[cur] += w[cur];for (auto i : G[cur]) {dfs(i);siz[cur] += siz[i];//用于剪枝for (int j = min(siz[cur], t - 1); j >= w[cur]; j--)for (int k = 0; k <= min(siz[i], j - w[cur]); k++)dp[cur][j] = max(dp[cur][j], dp[i][k] + dp[cur][j - k]);//这种板板板板子的转移方程不多赘述}
答案
就是根节点的计数呗，但是注意可用时间只有 \(t-1\) 秒。
故答案为
\[dp_{1,t-1}
\]
完整code
code
/*********************************************************** Author : dingziyang888* Website : https://www.luogu.com.cn/problem/* Created Time :* FileName :* Warning!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!* 1.MLE?* 2.array size enough?* 3.long long?* 4.overflow long long?* 5.multiple task cleaned?* 6.freopen?* 7.TLE?* *******************************************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
#define I using
#define AK namespace
#define IOI std
#define A return
#define C 0
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
I AK IOI;using ll = long long;
using ull = unsigned long long;
using lb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;constexpr int mod = 998244353;
constexpr int maxn = 205;
constexpr int maxk = 6005;int t, tot;int w[maxn], val[maxn];
int dp[maxn][maxk], siz[maxn];vector<int> G[maxn << 1];//树int build() {int w1, w2, cur = ++tot;cin >> w1 >> w2;w[cur] = w1 * 2;if (w2)val[cur] = w2;else {int l = build();//递归建树G[cur].push_back(l);//左子树int r = build();//递归建树G[cur].push_back(r);//右子树}return cur;
}//建树void dfs(int cur) {int p = min(t - 1, w[cur]);dp[cur][0] = dp[cur][p] = 0;if (val[cur]) {siz[cur] += val[cur] * 5;for (int i = w[cur]; i < max(siz[cur] + 1, t); i++)dp[cur][i] = min((i - w[cur]) / 5, val[cur]);//初始化我直接写里面了}siz[cur] += w[cur];for (auto i : G[cur]) {dfs(i);siz[cur] += siz[i];for (int j = min(siz[cur], t - 1); j >= w[cur]; j--)for (int k = 0; k <= min(siz[i], j - w[cur]); k++)dp[cur][j] = max(dp[cur][j], dp[i][k] + dp[cur][j - k]);//板板板板子}
}int main() {fast;freopen("std.in", "r", stdin);freopen("std.out", "w", stdout);cin >> t;build();//建树dfs(1);//DPcout << dp[1][t - 1];//输出A C;//这个玩意保好运
}