Description

Input

Output

Sample Input

7 9
39 6
13 2
22 6
7 4
-19 5
28 6
-17 1
2 1
3 2
4 1
5 4
6 2
7 3

Sample Output

52

Data Constraint

Solution

• 這是一道經(jīng)典的樹(shù)形依賴DP（背包問(wèn)題），即選取一個(gè)物品需要先選另一個(gè)物品。

• 設(shè) F[i][j] 表示做到第 i 點(diǎn)、已使用的費(fèi)用為 j 的最大價(jià)值。

• 則顯然有：

  F[i][j]=max{F[son][j?p[i]]+v[i]}

• 轉(zhuǎn)移即可，時(shí)間復(fù)雜度：O(NM) 。

Code

#include<cstdio> using namespace std; const int N=2001; int n,m,tot,ans; int first[N],next[N<<1],en[N<<1]; int v[N],p[N],f[N][N*5]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline int max(int x,int y) {return x>y?x:y; } inline void insert(int x,int y) {next[++tot]=first[x];first[x]=tot;en[tot]=y; } inline void dfs(int x,int y,int z) {if(z<=0) return;for(int i=first[x];i;i=next[i])if(en[i]!=y){for(int j=z-p[en[i]];j>=0;j--) f[en[i]][j]=f[x][j];dfs(en[i],x,z-p[en[i]]);for(int j=z;j>=p[en[i]];j--) f[x][j]=max(f[x][j],f[en[i]][j-p[en[i]]]+v[en[i]]);} } int main() {n=read(),m=read();for(int i=1;i<=n;i++) v[i]=read(),p[i]=read();for(int i=1;i<n;i++){int x=read(),y=read();insert(x,y);insert(y,x);}dfs(1,0,m);for(int i=m-p[1];i;i--) ans=max(ans,f[1][i]);if(m>=p[1]) ans+=v[1];printf("%d",ans);return 0; } 與50位技術(shù)專家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5344. 【NOIP2017模拟9.3A组】摘果子的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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