Luogu P1270 “访问”美术馆

题目传送门

树形DP套路题

---

输入比较有趣

转移方程还是套路的使用类似于(01)背包的形式：
dp[pos][j] = max(dp[pos][j], dp[pos][j-k] + dp[to][k-len])
dp[pos][j]表示在(pos)这个节点上已经偷了(j)幅画，(to)表示要去的节点，(len)是在走廊上浪费的时间

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
struct zzz {
    int t, nex, len;
}e[1010 << 1]; int head[1010], tot;
void add(int x, int y, int z) {
    e[++tot].t = y;
    e[tot].nex = head[x];
    e[tot].len = z;
    head[x] = tot;
}
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
      k = k * 10 + c - 48, c = getchar();
    return k * f;
}
int s, cnt, son[1010], dp[1010][1010];
void input(int fa) {  //有趣的输入
    int x = read(), y = read();
    ++cnt; int pos = cnt;
    add(fa, pos, x << 1);
    //cout << fa << " " << pos << endl;
    if(!y) input(pos), input(pos);
    else son[pos] = y;
}
void dfs(int pos) {  // dp
    if(son[pos]) { // 初始化，也就是边界条件
        for(int i = 5; i <= s; ++i) dp[pos][i] = min(dp[pos][i-5] + 1, son[pos]);
        return ;
    }
    for(int i = head[pos]; i; i = e[i].nex) { //状态转移
        dfs(e[i].t);
        for(int j = s; j >= e[i].len; --j)
            for(int k = e[i].len; k <= j; ++k)
                dp[pos][j] = max(dp[pos][j], dp[pos][j-k] + dp[e[i].t][k-e[i].len]);
    }
}
int main() {
    s = read() - 1;
    input(0);
    dfs(0);
    cout << dp[0][s];
    return 0;
}

彩蛋

十分类似的题目：Luogu P3360 偷天换日