題目背景

神偷對(duì)藝術(shù)館內(nèi)的名畫(huà)垂涎欲滴準(zhǔn)備大撈一把。

題目描述

藝術(shù)館由若干個(gè)展覽廳和若干條走廊組成。每一條走廊的盡頭不是通向一個(gè)展覽廳，就

是分為兩個(gè)走廊。每個(gè)展覽廳內(nèi)都有若干幅畫(huà)，每副畫(huà)都有一個(gè)價(jià)值。經(jīng)過(guò)走廊和偷畫(huà)都是

要耗費(fèi)時(shí)間的。

警察會(huì)在n 秒后到達(dá)進(jìn)口，在不被逮捕的情況下你最多能得到的價(jià)值。

輸入格式

第一行一個(gè)整數(shù) n(n≤600)。

第二行若干組整數(shù)，對(duì)于每組整數(shù)（t,x），t 表示進(jìn)入這個(gè)展覽廳或經(jīng)過(guò)走廊要耗費(fèi) t

秒的時(shí)間，若x>0 表示走廊通向的展覽廳內(nèi)有x 幅畫(huà),接下來(lái)

x對(duì)整數(shù)(w,c)表示偷一幅價(jià)值為 w 的畫(huà)需要 c秒的時(shí)間。若

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

輸入是按深度優(yōu)先給出的。房間和走廊數(shù)不超過(guò) 300 個(gè)。

輸出格式

僅一個(gè)整數(shù)，表示能獲得的最大價(jià)值。

輸入輸出樣例

輸入 #1復(fù)制

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

輸出 #1復(fù)制

1500

這個(gè)傻逼題的讀入有坑，邊讀遍處理，靠！

#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; }

總結(jié)

以上是生活随笔為你收集整理的洛谷P3360偷天换日（树形DP）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。