hdu 1011 Starship Troopers

/*
    树形dp
    题意：
    给出一颗树，每个节点都有敌人，消灭敌人后会给报酬，自己的士兵一个能消灭20个，从节点1开始，如果根节点消灭，子节点就不消灭
    给出一个n表示有n个节点，m表示自己士兵的数量，接下来n行，表示n个节点敌人的数量和报酬，接下来n-1行是树的情况
*/
#include<stdio.h>
#include<string.h>
const int maxn = 105;
int N,M,first[maxn],next[maxn<<1],bug[maxn],fra[maxn],ne,flag[maxn],dp[maxn][maxn];//dp[i][j]表示以i为跟节点的子树安排j个士兵的最大价值，first，next是邻接表，bug，fra是节点的敌人和报酬，
struct Edge
{
    int u,v;
    void set(int u,int v)
    {
        this->u=u;
        this->v=v;
    }
}ed[maxn<<1];
void add_Edge(int u,int v)
{
    ed[ne].set(u,v);
    next[ne]=first[u];
    first[u]=ne++;
}
void dfs(int u)
{
    flag[u]=1;
    int temp=(bug[u]+19)/20;
    for(int i=temp;i<=M;i++) dp[u][i]=fra[u];
    for(int i=first[u];i+1;i=next[i])
    {
        int v=ed[i].v;
        if(flag[v]) continue;
        dfs(v);
        for(int j=M;j>=temp;j--)//因为是一直在一次for循环中，一直都是u，和v，所以要想0,1背包的一维一样从大的开始，这样就避免了重复装
        {
            for(int k=1;k<=j-temp;k++)
                if(dp[u][j]<dp[u][j-k]+dp[v][k])//因为不管u的其他子节点是否排了人，当前这个点v一定没有排人
                    dp[u][j]=dp[u][j-k]+dp[v][k];
        }
    }
}
int main()
{
    while(scanf("%d%d",&N,&M)!=EOF&&(N+1))
    {
        for(int i=1;i<=N;i++)
            scanf("%d%d",&bug[i],&fra[i]);
        ne=0;
        memset(first,-1,sizeof(first));
        memset(dp,0,sizeof(dp));
        memset(flag,0,sizeof(flag));
        for(int i=0;i<N-1;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add_Edge(u,v);
            add_Edge(v,u);
        }
        if(M==0)
        {
            printf("0n");
            continue;
        }
        dfs(1);
        printf("%dn",dp[1][M]);
    }
    return 0;
}

最后

以上就是傲娇电话为你收集整理的hdu 1011 Starship Troopers的全部内容，希望文章能够帮你解决hdu 1011 Starship Troopers所遇到的程序开发问题。

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