P1270 “访问”美术馆

题目描述

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

输入格式

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

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

输出格式

输出最多能偷到的画的数量。

输入输出样例 #1

输入 #1

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

输出 #1

2

参考代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int MXT = 6005;      // 最大时间 +1
const int MXN = 205;       // 最大结点数(2*leaf-1)
int dp[MXN][MXT];          // 动态规划表
int seq[MXN*2];            // 输入序列
int pos=0, tot=0;          // 读入游标与长度
int lim;                   // T-1
int idn=0;                 // 结点编号递增

// 返回当前子树编号
int dfs(){
    int id = idn++;                    // 为本结点分配编号
    int w = seq[pos++];                // 单程时间
    int p = seq[pos++];                // 画数，0=分叉

    int cur[MXT];                      // 临时数组
    fill(cur,cur+lim+1,-1);

    if(p>0){                           // 叶子
        cur[0]=0;
        for(int k=1;k<=p;++k){
            int t=5*k;
            if(t<=lim) cur[t]=k;
        }
    }else{                             // 内部结点
        int L=dfs(), R=dfs();          // 左右子树
        cur[0]=0;
        for(int i=0;i<=lim;++i) if(dp[L][i]>=0)
            for(int j=0;i+j<=lim;++j) if(dp[R][j]>=0)
                cur[i+j]=max(cur[i+j],dp[L][i]+dp[R][j]);
    }

    // 将往返当前走廊的 2*w 时间映射到全局时间轴
    fill(dp[id],dp[id]+lim+1,-1);
    dp[id][0]=0;                       // 可以不走
    for(int t=0;t<=lim;++t)
        if(cur[t]>=0 && t+2*w<=lim)
            dp[id][t+2*w]=max(dp[id][t+2*w],cur[t]);

    return id;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T;
    if(!(cin>>T)) return 0;
    lim = T-1;                         // 留 1 秒逃跑

    int x;
    while(cin>>x) seq[tot++]=x;

    int rt = dfs();                    // 根结点
    int ans = 0;
    for(int t=0;t<=lim;++t) ans=max(ans,dp[rt][t]);
    cout<<ans<<"\n";
    return 0;
}

参考代码

代码来自> -

#include <iostream>
#include <cmath>
using namespace std;

const int Maxn = 200 + 5;
const int Maxm = 6000 + 5;

int vct[2 * Maxn], dp[Maxn][Maxm], m, cnt = 0, pos = 0; // dp[i][j] = 以i为根的子树用时j秒（包括回到i的时间）可以偷的最大画数

int dfs() {
    int root = ++cnt, ti = vct[++pos], num = vct[++pos];
    ti <<= 1;
    if (num != 0) {
        for (int i = ti; i <= m; ++i)  dp[root][i] = min((i - ti) / 5, num);
        return root;
    }

    int left = dfs();
    int right = dfs();

    for (int i = ti; i <= m; ++i) {
        for (int j = 0; j <= i - ti; ++j)
            dp[root][i] = max(dp[root][i], dp[left][j] + dp[right][i - ti - j]);
    }

    return root;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t, x, id = 0;
    if (!(cin >> t))  return 0;
    m = t - 1;

    while (cin >> x)  vct[++id] = x;

    int root = dfs();

    cout << dp[root][m];

    return 0;
}