题解 P1270 【“访问”美术馆】

· · 题解

显然的树形dp，但是——

为什么要人云亦云呢？写成记忆化搜索不好么？短的优美。

先上代码（具体解释在代码下面）：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
template<class T>void ChkMax(T &a,T b){if (a<b)a=b;}
const int N=1010;
int dp[N][N];
struct TreeNode{
    int cost,val;
}T[N*10];
int tot;
void init(int x){
    scanf("%d%d",&T[x].cost,&T[x].val);
    T[x].cost*=2;
    if (!T[x].val){
        init(x<<1);init(x<<1|1);
    }
}
int dfs(int x,int tot){
    if (dp[x][tot]>0 || !tot)return dp[x][tot];
    if (T[x].val)return dp[x][tot]=min(T[x].val,(tot-T[x].cost)/5);
    for (int k=0;k<=tot-T[x].cost;k++)
        ChkMax(dp[x][tot],dfs(x<<1,k)+dfs(x<<1|1,tot-T[x].cost-k));
    return dp[x][tot];
}
int main(){
    scanf("%d",&tot);tot--;
    init(1);
    printf("%d",dfs(1,tot));
    return 0;
}

好了，来说说怎么搞这道题吧。

首先处理读入，以dfs的形式输入，很新颖。

然后考虑一个简单的dp[i][j]表示到第i条走廊剩余j的时间最多能拿的画的数量。

那么枚举一下分给左儿子的时间k，那么分给右儿子的就是j-k了。

所以dp[i][j]=max(dp[i][j],dp[lch][k]+dp[rch][j-k])

当然，还要减去一个经过走廊的时间。注意，走廊是要走过去并且走回来的，所以时间在读入时*2就行了。

题目还有一个坑，就是警察一到小偷就死，所以小偷必须在警察来的前1秒跑掉【手动滑稽】

所以读入的时间要-1