【CodeVS 1163】“访问”艺术馆(gallery)/ 题解

【CodeVS 1163】“访问”艺术馆(gallery)/ 题解

Origin

Statement

Peel was a famous pirate painter. After months of careful preparation, he planned to steal art at the museum. In the structure of the museum, each hallway is either bifurcated into two corridors or leads to an exhibition room. Peel knew the number of paintings in each exhibition room, and he accurately measured the time of passing through each hallway. Due to his experience, he took the next painting for 5 seconds. Your task is to design a program that calculates how many paintings he can steal before the police arrive.

Example

Idea

很裸的树形DP。因为题目给的是二叉树,直接在DFS的时候枚举分配给左右儿子的时间就好了。。。

Code

#include 
using namespace std;
int f[207][607],Tlim,id;
void dfs(int u){
    int len,x;cin>>len>>x;
    len*=2;if (x){
        for (int i=len;i<=Tlim;i++)
            f[u][i]=min(x,(i-len)/5);
        return;
    }
    int l=++id,r=++id,dfs(l),dfs(r);
    for (int i=len;i<=Tlim;i++)
        for (int j=0;j<=i-len;j++)
            f[u][i]=max(f[u][i],f[l][j]+f[r][i-len-j]);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>Tlim;
    dfs(0);
    cout<