现在的位置: 首页 > 综合 > 正文

hdu 1011 (树形DP)

2018年12月28日 ⁄ 综合 ⁄ 共 984字 ⁄ 字号 评论关闭

dp[i][j]:在i节点用j个士兵,得到的brain

dp[i][j]=dp[i][j-k]+dp[son[i]][k];

跟背包是一样的思想





#include<stdio.h>
#include<string.h>
#define N 110
int dp[N][N],head[N],num,bug[N],brain[N],n,m,vis[N];
//dp[i][j]:在i节点用j个士兵,得到的brain
//dp[i][j]=dp[i][j-k]+dp[son[i]][k];
struct edge
{
    int st,ed,next;
}E[N*2];
void addedge(int x,int y)
{
    E[num].st=x;
    E[num].ed=y;
    E[num].next=head[x];
    head[x]=num++;
}
void dfs(int u)
{
    int i,j,k,v;
    vis[u]=1;
    int temp;
    temp=bug[u]/20;
    if(bug[u]%20!=0)
        temp++;
    for(i=temp;i<=m;i++)
        dp[u][i]=brain[u];
    for(i=head[u];i!=-1;i=E[i].next)
    {
         v=E[i].ed;
        if(vis[v]==1)continue;
        dfs(v);
        for(j=m;j>=temp;j--)
        {
            for(k=1;j+k<=m;k++)
            {
                if(dp[v][k]>0&&dp[u][j+k]<dp[u][j]+dp[v][k])
                    dp[u][j+k]=dp[u][j]+dp[v][k];
            }
        }
    }
}
int main()
{
    int i,x,y;
    while(scanf("%d%d",&n,&m),n>=0&&m>=0)
    {
        for(i=1;i<=n;i++)
            scanf("%d%d",&bug[i],&brain[i]);
        memset(head,-1,sizeof(head));
        num=0;
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            addedge(x,y);
            addedge(y,x);
        }
        if(m==0)
        {
            printf("0\n");
            continue;
        }
        memset(vis,0,sizeof(vis));
        memset(dp,0,sizeof(dp));
        dfs(1);
        printf("%d\n",dp[1][m]);
    }
    return 0;
}

抱歉!评论已关闭.