洛谷P1270 “访问”美术馆 题解

题目链接：P1270 “访问”美术馆

题意：

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

显然的树上背包题，还是个二叉树

读入可以用dfs，然后走廊耗时肯定要变原来两倍

设 $dp[u][j]$ 表示 $u$ 所在子树花不超过 $j$ 秒能获得的最大价值，则

$$dp[u][j] = \max(dp[u][j],dp[\text{ls}][j-k-\text{w}[u]]+dp[\text{rs}][k])$$

如果 $u$ 是叶子结点的话，可以枚举它的耗时然后算能拿几幅画

for(int i=0; i/5<=val[u]&&w[u]+i<=m; i++)
    dp[u][w[u]+i]=i/5;

时间复杂度 $O(nm)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(615)

int m,w[N],sz[N],val[N],tmp[N],dp[N][N];
void init(int u)
{
    cin >> w[u] >> val[u];w[u]<<=1;
    if(!val[u])
        init(u<<1),init(u<<1|1);
}
void dfs(int u)
{
    if(val[u])
    {
        for(int i=0; i/5<=val[u]&&w[u]+i<=m; i++)
            dp[u][w[u]+i]=i/5;
        return;
    }
    dfs(u<<1);dfs(u<<1|1);
    for(int j=w[u]; j<=m; j++)
        for(int k=0; k+w[u]<=j; k++)
            dp[u][j]=max(dp[u][j],dp[u<<1][j-w[u]-k]+dp[u<<1|1][k]);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> m;--m;
    init(1);dfs(1);
    cout << dp[1][m] << '\n';
    return 0;
}