Themore,TheBetter树形dp-创新互联

树形dp 

dp[i][j] 代表以i为根节点 包含根节点的 有j个城堡

创新互联建站专注于海口企业网站建设,响应式网站开发,商城网站制作。海口网站建设公司,为海口等地区提供建站服务。全流程按需开发网站，专业设计，全程项目跟踪，创新互联建站专业和态度为您提供的服务

f[i][j] 代表以i为根节点 不包含根节点 的 j个城堡

View Code

The more, The Better

Time Limit :6000/2000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) :1   Accepted Submission(s) : 1
Font: Times New Roman| Verdana | Georgia
Font Size: ← →
Problem Description
ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？
Input
每个测试实例首先包括2个整数，N,M.(1 <= M <= N <= 200);在接下来的N行里，每行包括2个整数，a,b. 在第 i 行，a 代表要攻克第 i 个城堡必须先攻克第 a 个城堡，如果 a = 0 则代表可以直接攻克第 i 个城堡。b 代表第 i 个城堡的宝物数量, b >= 0。当N = 0, M = 0输入结束。
Output
对于每个测试实例，输出一个整数，代表ACboy攻克M个城堡所获得的最多宝物的数量。
Sample Input
3 20 10 20 37 42 20 10 42 17 17 62 20 0
Sample Output
513

#include 
#include
#include

struct node
{
int index ;
    node*next ;
}adj[205];
bool vis[205];
int dp[205][205], f[205][205], w[205], n, m;
void add(int x, int y)
{
    node*p = new node;
    p->index = y;
    p->next = adj[x].next;
    adj[x].next= p;
}
int max(int a, int b)
{return a>=b ?a :b ; }
void dfs(int now)
{
int i;
    vis[now]= 1;
    node*p = adj[now].next;
while( p!=NULL && !vis[p->index] )
    {
        dfs(p->index);

for(i=m; i>=1; i--) // 一定要逆序！ f[i][j]没处理前为0 for(int j=1; j<=i; j++)
            {
                f[now][i]= max(f[now][i], f[now][i-j] + dp[p->index][j]);
            }
        p= p->next;
    }
for(i=1; i<=m; i++)
        dp[now][i]= f[now][i-1] + w[now];
}
int main()
{
int i, a;
while(scanf("%d %d", &n, &m), m|n)
    {
        memset(dp,0, sizeof(dp));
        memset(f,0, sizeof(f));
        memset(vis,0, sizeof(vis));
for(i=0; i<=n; i++)
        {
            adj[i].next= NULL;
        }
for(i=1; i<=n; i++)
        {
            scanf("%d %d", &a, &w[i]);
            add(a, i);
        }
        dfs(0);
        printf("%d
", f[0][m]);
    }
return 0;
}

名称栏目：Themore,TheBetter树形dp-创新互联
网站URL：http://6mz.cn/article/jijsg.html