做题笔记 “访问“美术馆 P1270

这是一道树形DP

洛谷的链接

代码

#include<bits/stdc++.h> using namespace std; int n,cur; int f[1010][1010]; void dfs(){ int w,num,now = ++cur; cin >> w >> num; w <<= 1;/来回乘以2 if(num){ for(int t = w;t <= n;++t){ f[now][t] = min((t-w)/5,num); /* 这里写的很优雅 解释一下 num是画的数量，f[now][t]不会超过num，而当时间短时，就只可取(t-w)/5 */ } }else{ int left,right; left = cur+1; dfs(); right = cur+1; dfs();//奇妙的标号，下面会讲 for(int t = w;t <= n;++t){ for(int lt = 0;lt <= t-w;++lt){ f[now][t] = max(f[now][t],f[left][lt]+f[right][t-w-lt]);//枚举分给左右子树的时间 } } } } int main(){ ios::sync_with_stdio(0); cin >> n; --n;//大坑！当t = n时,会被抓住，所以-1 dfs(); cout << f[1][n]; return 0; }

分析

不难看出这是一珂二叉树 通过了奇妙的读入和神奇的标数解决了这一题

基本思想

$$f(i,j)表示当子树的根节点为i，时间为j时的最大值。$$ 分为叶子结点和非叶子结点处理，叶子结点枚举时间取个数，非叶子结点枚举左右子树分配的时间。

奇妙的标数

只要标数统一就不会出错