洛谷P1270 “访问”美术馆

@Pelom  November 11, 2019

题意

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

题解

树上背包
注意读入

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1000+10;
int n;
int sz;
int dp[N][N];
void dfs(){
    int rt=++sz,t,w;
    scanf("%d%d",&t,&w);
    t<<=1;
    if(w){
        for(int i=t;i<=n;i++)
            dp[rt][i]=min((i-t)/5,w);
        return ;
    }
    int ls=sz+1;
    dfs();
    int rs=sz+1;
    dfs();
    for(int i=t;i<=n;i++)
        for(int j=0;j<=i-t;j++)
            dp[rt][i]=max(dp[rt][i],dp[ls][j]+dp[rs][i-t-j]);
}
int main(){
    scanf("%d",&n);
    n--;
    dfs();
    printf("%d",dp[1][n]);
    return 0;
}

添加新评论