方法挖掘——P1270 “访问”美术馆

· · 个人记录

题面

题目描述

经过数月的精心准备，Peer Brelstet，一个出了名的盗画者，准备开始他的下一个行动。艺术馆的结构，每条走廊要么分叉为两条走廊，要么通向一个展览室。Peer知道每个展室里藏画的数量，并且他精确测量了通过每条走廊的时间。由于经验老到，他拿下一幅画需要5秒的时间。你的任务是编一个程序，计算在警察赶来之前，他最多能偷到多少幅画。

输入输出格式

输入格式：

第1行是警察赶到的时间，以s为单位。第2行描述了艺术馆的结构，是一串非负整数，成对地出现：每一对的第一个数是走过一条走廊的时间，第2个数是它末端的藏画数量；如果第2个数是0，那么说明这条走廊分叉为两条另外的走廊。数据按照深度优先的次序给出，请看样例。

一个展室最多有20幅画。通过每个走廊的时间不超过20s。艺术馆最多有100个展室。警察赶到的时间在10min以内。

输出格式：

输出偷到的画的数量

输入输出样例

输入样例

60
7 0 8 0 3 1 14 2 10 0 12 4 6 2

输出样例

2

头脑风暴

纪念我为数不多的独立A掉的一道蓝题。

显然路径是二叉树一棵树，那么我就想到了树形dp。

不过这道题居然还考我语文。。。

正确解法

建树：这个边权和点权好像有点乱，于是我把走廊当成点来看，展览室里的画就属于通往该展览室的走廊的点权的一部分。这样再把根连一个点表示大门，就成了一棵根的度为1，其他结点度为2的树了。

方程：设dp[i][j]为在j时间内，从i开始走以i为根结点的子树然后再回到i，最大的贡献。如果i不是根或者叶子，那么dp[i][j] = max\{dp[l][j-2T_l], dp[r][j-2T_r], dp[l][k] + dp[r][j-2T_l-2T_r - k]\}。就是我走左儿子，但是走到要花一段时间，回来要花一段时间，能够在左儿子里有用的时间就减少了两倍的路程时间，右儿子同理。两个都走的话我就要走两个儿子的双倍路程，同理减去。如果i是根(i==0)，那么dp[0][j] = dp[1][j-2T_1]。就是走到第一个路口再返回用的时间，理由同上。 如果i是叶子，那么就用现在还有的时间算一下最多能拿多少。

注意答案是dp[0][t-1]，因为题目说的是“在警察来之前”，dp[0][t]警察已经来了，是“警察来之时”，不合题意(这个点肯定坑了好多人)。

因为循环层数好像有点高，还分析了一下复杂度。每个点遍历一次，每次都要访问t个时间，然后非叶结点要枚举时间，所以复杂度是O(nt^2)，其中n是结点个数，n = n_2 + n_1 + n_0 = n_2+n_0 = 2n_0+1，n_0就是展览室数量，所以复杂度约是T(200600600) = T(7.2e7) = 能过。

算法实现

#include <cstdio>
#define max(x, y) x > y ? x : y

const int maxn = 300;
const int maxt = 610;

int  t;
int dp[maxn][maxt];

struct Tree {
    int t, n, l, r;
} tree[maxn];
int m = 0;

int Build() {
    int tt, n, id = ++m;
    scanf("%d%d", &tt, &n);
    tree[id].t = tt, tree[id].n = n;
    if (!n) {
        tree[id].l = Build();
        tree[id].r = Build();
    }
    return id;
}

void dfs(int v) {
    if (v == 0) {
        dfs(1);
        for (int j = t; j >= tree[1].t << 1; j--)
            dp[v][j] = dp[1][j - (tree[1].t << 1)];
        return;
    }
    if (tree[v].n) {
        int n = tree[v].n;
        for (int j = t; j >= 0; j--)
            dp[v][j] = j/5 < n ? j/5 : n; 
        return;
    }
    int lc = tree[v].l, rc = tree[v].r;
    int lt = tree[lc].t << 1, rt = tree[rc].t << 1;
    dfs(lc), dfs(rc);
    for (int j = t; j >= 0; j--) {
        int ans = 0;
        if (j >= lt)
            ans = max(ans, dp[lc][j-lt]);
        if (j >= rt)
            ans = max(ans, dp[rc][j-rt]);
        if (j >= lt + rt) {
            for (int k = 0; k <= j-lt-rt; k++)
                ans = max(ans, dp[lc][k] + dp[rc][j-lt-rt-k]);
        }
        dp[v][j] = ans;
    }
}

int main() {
    scanf("%d", &t);
    Build();
    dfs(0);
    printf("%d", dp[0][t-1]);
    return 0;
}