【NOIP2017模拟9.3A组】摘果子

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

Solution

就是树上背包问题，有一个很经典的做法
按照dfs序反着来dp，那么f[i][j]表示的就是dfs序为i的点，受了j的毒的值
如果i这个点选，那么f[i][j]可以从f[i+1][j-p[i]]转移过来
否则可以从f[跨过i这个子树的下一个值][j]转移过来
为什么是正确的呢？
显然只选子树或只选兄弟是正确的
但是又要选子树又要选兄弟呢？
会发现到我子树的dfs最大的一个点的时候，它会将它+1的位置转移过来，也就是把兄弟转移了过来
那么又选子树又选兄弟就包含在选子树中了

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 20100
using namespace std;
int n,m,a[N],b[N],f[4050][4050],last[N],next[N],to[N],tot=0,dfn[N],ls[N],c[N];
void putin(int x,int y)
{

next[++tot]=last[x];last[x]=tot;to[tot]=y;
}
void dg(int x)
{

dfn[x]=++tot;c[tot]=x;

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

{

if(dfn[to[i]]) continue;

dg(to[i]);

}

ls[x]=tot;
}
int main()
{

scanf("%d%d",&n,&m);

fo(i,1,n) scanf("%d%d",&a[i],&b[i]);

fo(i,1,n-1)

{

int x,y;scanf("%d%d",&x,&y);

putin(x,y);putin(y,x);

}

tot=0;

dg(1);

fd(i,n,1)

{

fo(j,0,m)

{

if(j>=b[c[i]])f[i][j]=max(f[i][j],f[i+1][j-b[c[i]]]+a[c[i]]);

f[i][j]=max(f[i][j],f[ls[c[i]]+1][j]);

}

}

int ans=0;

fo(i,0,m) ans=max(ans,f[1][i]);

printf("%d",ans);
}

最后

以上就是小巧御姐为你收集整理的【NOIP2017模拟9.3A组】摘果子的全部内容，希望文章能够帮你解决【NOIP2017模拟9.3A组】摘果子所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。