BZOJ1017 樹形DP

2022-09-22 05:46:43 字數 2347 閱讀 2317

time limit: 30 sec  memory limit: 162 mb

submit: 2308  solved: 919

[submit][status][discuss]

dotr (defense of the robots) allstars是一個風靡全球的魔獸地圖,他的規則簡單與同樣流行的地圖dota

(defense of the ancients) allstars。dotr裡面的英雄只有一個屬性——力量。他們需要購買裝備來提升自己的

力量值,每件裝備都可以使佩戴它的英雄的力量值提高固定的點數,所以英雄的力量值等於它購買的所有裝備的力

量值之和。裝備分為基本裝備和高階裝備兩種。基本裝備可以直接從商店裡面用金幣購買,而高階裝備需要用基本

裝備或者較低階的高階裝備來合成,合成不需要附加的金幣。裝備的合成路線可以用一棵樹來表示。比如,sange

and yasha的合成需要sange,yasha和sange and yasha recipe scroll三樣物品。其中sange又要用ogre axe, belt

of giant strength和 sange recipe scroll合成。每件基本裝備都有數量限制,這限制了你不能無限制地合成某

些價效比很高的裝備。現在,英雄spectre有m個金幣,他想用這些錢購買裝備使自己的力量值儘量高。你能幫幫他

嗎?他會教你魔法haunt(幽靈附體)作為回報的。

第一行包含兩個整數,n (1 <= n <= 51) 和 m (0 <= m <= 2,000)。分別表示裝備的種類數和金幣數。裝備

用1到n的整數編號。接下來的n行,按照裝備1到裝備n的順序,每行描述一種裝備。每一行的第一個非負整數表示這

個裝備貢獻的力量值。接下來的非空字元表示這種裝備是基本裝備還是高階裝備,a表示高階裝備,b表示基本裝備

。如果是基本裝備,緊接著的兩個正整數分別表示它的單價(單位為金幣)和數量限制(不超過100)。如果是高

級裝備,後面緊跟著一個正整數c,表示這個高階裝備需要c種低階裝備。後面的2c個數,依次描述某個低階裝備的

種類和需要的個數。

第一行包含一個整數s,表示最多可以提升多少點力量值。

10 59

5 a 3 6 1 9 2 10 1

1 b 5 3

1 b 4 3

1 b 2 3

8 a 3 2 1 3 1 7 1

1 b 5 3

5 b 3 3

15 a 3 1 1 5 1 4 1

1 b 3 5

1 b 4 3

33//先標明參考**

大體上就是好幾個子樹,然後對子樹進行dp的樣子,沒有建立虛擬根節點,也是用子節點的狀態去更新父節點的狀態,細節見**。

#include#include

#include

const

int inf=1e9;

using

namespace

std;

intn,m,cnt,tot,ans;

int p[55],l[55],m[55

];int f[55][105][2005

];int g[55][2005],h[55][2005

];char ch[5

];int last[55],deg[55

];struct datae[20008

];void insert(int u,int v,int

w) void dp(int

x)     l[x]=inf;

for(int i=last[x];i;i=e[i].next)

l[x]=min(l[x],m/m[x]);

memset(g,-0x3f3f3f3f,sizeof

(g));

g[0][0]=0;//

表示x的前i個兒子的子樹,花費j的錢,所能獲得的最大力量

for(int l=l[x];l>=0;--l)

for(int j=0;j<=l;++j)//

***此處for迴圈的方向沒有影響***

for(int k=0;k<=m;++k)

f[x][j][k]=max(f[x][j][k],g[tot][k]+p[x]*(l-j));  //

對f進行更新}}

intmain()

}else scanf("

%d%d

",&m[i],&l[i]);

}for(int x=1;x<=n;++x)

}for(int i=0;i<=m;++i)

ans=max(ans,h[tot][i]);

printf(

"%d\n

",ans);

}

codevs 1017 乘積最大 dp

時間限制 1 s 空間限制 128000 kb 今年是國際數學聯盟確定的 2000 世界數學年 ,又恰逢我國著名數學家華羅庚先生誕辰90週年...

BZOJ 1571 DP

思路 預處理出在能力值為i的時候 滑雪一次的最小時間 f i j 表示i時間 j的能力值 最多的滑雪次數 我先用vector 把課程按起點push進去 1 for int k 0 k上課 2 f i 1 j max f i j f i 1 j 喝一杯可可汁 3 f i land j j max f ...

DP bzoj 1218

time limit 10 sec memory limit 162 mb submit 1292 solved 621 submit status discuss 一種新型的鐳射炸彈,可以摧毀一個邊長為r的正方形內的所有的目標。現在地圖上有n n 10000 個目標,用整數xi yi 其值在 0 ...