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

· · 题解

0.说在前面

仔细检查了一下自己的做法和前面的题解们都有一些或大或小的差异，决定详细地分享给大家。

如果是因为莫名WA掉了某些点而点进来的，那么请检查一下

1.思路分析 和 代码实现

每条走廊分叉为两条走廊？ ——树形结构
在规定的时间（价值）内拿走多少画（物品）？ ——背包

一道非常好的树形背包上手题。当然也可以用爆搜实现，但是其复杂度更高，并不推荐用在这里。

Part 1 .读入

很新颖的读入方式，先序遍历读入。我们可以使用指针，每条走廊开两个指针分别指向儿子们，但这样略显麻烦。
更好的方法是像线段树一样，把二叉树改为线性存储，节点x的儿子的编号分别为x<<1和x<<1|1。此方法的优点在于，无需再存储儿子编号，而且时间效率极高。为避免下标越界记得开两倍空间。
另外，刚刚也已经提到每条走廊必须走两次，我们不妨在读入的时候就直接把时间乘2，省去后顾之忧。

void build(int x){
    scanf("%d%d",&t[x],&a[x]);
    t[x]<<=1;   //非常重要，每条走廊必须走两次
    if(!a[x])build(x<<1),build(x<<1|1);  //如果尽头没有画，读左右儿子走廊
}

Part 2. 背包

节点分为两类，一类是没画的走廊，一类是有画的展厅。不妨设f[x][t]表示x号节点在第t秒可以投多少幅画。
在以下的代码中，tim 指到达x号节点末端所需要的时间；m指警察到的时间减1（因为你只能偷这么久）

我们先讨论展厅。很显然每幅画只能偷一次，因此最多偷 a[x]幅。偷一幅画需要五秒，于是我们可以很容易的得到转移方程f[x][t]=f[x][t-5]+1。

for(int i=1;i<=a[x];++i){  //枚举偷1副到全部偷完
    int now=tim+(i*5); 
    if(now>m)break;   //你必须在警察来之前逃走
    f[x][now]=f[x][now-5]+1;
}

我们再讨论更复杂的走廊。由于先偷左儿子和先偷右儿子没有本质区别，所以我们一律视为先偷左儿子。假设此人花了i秒在左儿子偷画，花了j秒在右儿子偷画。（如果没有去左/右儿子，那么i/j为0）由于他到达x号走廊的时刻是tim，所以他离开的时间是tim+i+j。因此我们可以得到方程 f[x][tim+i+j] = \text{max}( f[x][tim+i+j] , f[l][tim+i] + f[r][tim+j] )

int l=x<<1,r=x<<1|1;
dfs(l,tim+t[l]);  //先递归儿子，再回溯
dfs(r,tim+t[r]);
for(int i=0;i<=m-tim;++i)  //左儿子偷i秒
 for(int j=0;tim+i+j<=m;++j)  //右儿子偷j秒
  tomax(f[x][tim+i+j],f[l][tim+i]+f[r][tim+j]);

最后的答案应该是f[1][m]。注意 m 等于警察到达的时间减1哦。

2.完整代码

#include<cstdio>

int t[405],a[405],f[405][605],ans,m;

void build(int x){   //读入
    scanf("%d%d",&t[x],&a[x]);
    t[x]<<=1;
    if(!a[x])build(x<<1),build(x<<1|1);
}

inline void tomax(int &a,int b){if(a<b)a=b;}
void dfs(int x,int tim){   //树形DP主体
    if(!a[x]){
        int l=x<<1,r=x<<1|1;
        dfs(l,tim+t[l]);
        dfs(r,tim+t[r]);
        for(int i=0;i<=m-tim;++i)
         for(int j=0;tim+i+j<=m;++j)
          tomax(f[x][tim+i+j],f[l][tim+i]+f[r][tim+j]);
    }else{
        for(int i=1;i<=a[x];++i){
            int now=tim+(i*5);
            if(now>m)break;
            f[x][now]=f[x][now-5]+1;
        }
    }
}

int main(){
    scanf("%d",&m);--m;  //读入与预处理
    build(1);
    dfs(1,t[1]);
    printf("%d",f[1][m]);
    return 0;
}

3.写在后面

做完此题可以继续尝试很类似的 P3360 偷天换日

DP不易，多加练习