洛谷P3360偷天换日（树形DP）

题目背景

神偷对艺术馆内的名画垂涎欲滴准备大捞一把。

题目描述

艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅，就

是分为两个走廊。每个展览厅内都有若干幅画，每副画都有一个价值。经过走廊和偷画都是

要耗费时间的。

警察会在n 秒后到达进口，在不被逮捕的情况下你最多能得到的价值。

输入格式

第一行一个整数 n(n≤600)。

第二行若干组整数，对于每组整数（t,x），t 表示进入这个展览厅或经过走廊要耗费 t

秒的时间，若x>0 表示走廊通向的展览厅内有x 幅画,接下来

x对整数(w,c)表示偷一幅价值为 w 的画需要 c秒的时间。若

x=0 表示走廊一分为二。(t，c≤5; x≤30)

输入是按深度优先给出的。房间和走廊数不超过 300 个。

输出格式

仅一个整数，表示能获得的最大价值。

输入输出样例

输入 #1复制

50

5 0 10 1 10 1 5 0 10 2 500 1 1000 2 18 1 1000000 4

输出 #1复制

这个傻逼题的读入有坑，边读遍处理，靠！

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int n,m,dp[10000][10000];

int a[1000],b[1000];

void tree_DP(int x)

{

    int t1,t2;

    cin>>t1>>t2;

    t1*=2;

    if(t2>0)

    {

        for(int i=1; i<=t2; i++)

        {

            cin>>a[i]>>b[i];

        }

        for(int i=1; i<=t2; i++)

        {

            for(int j=n; j>=b[i]+t1; j--)

            {

                dp[x][j]=max(dp[x][j],dp[x][j-b[i]]+a[i]);

            }

        }

    }

    if(t2==0)

    {

        tree_DP(x*2);

        tree_DP(x*2+1);

        for(int j=t1; j<=n; j++)

        {

            for(int k=0; k<=j-t1; k++)

            {

                dp[x][j]=max(dp[x][j],dp[x*2][j-k-t1]+dp[x*2+1][k]);

            }

        }

        return;

    }

}

int main()

{

    cin>>n;

    n--;

    tree_DP(1);

    cout<<dp[1][n];

    return 0;

}

巴特西