当前位置:编程学习 > C/C++ >>

rnqoj-30- [stupid]愚蠢的矿工-树形DP

把树转化为二叉树,然后再左右DP;
 
#include<stdio.h>  
#include<string.h>  
#include<iostream>  
#include<algorithm>  
using namespace std;  
struct list  
{  
    int l;  
    int r;  
}node[2001];  
int val[2001];  
int vis[2001][101];  
int m,n;  
int dp(int x,int m)  
{  
    if(m==0)return 0;  
    if(vis[x][m]!=-1)return vis[x][m];  
    if(x==0)return 0;  
    int ans=0;  
    ans=dp(node[x].r,m);  
    for(int i=0;i<m;i++)  
    {  
        ans=max(ans,dp(node[x].l,i)+val[x]+dp(node[x].r,m-i-1));  
    }  
    vis[x][m]=ans;  
    return ans;  
}  
void init()  
{  
    int i;  
    scanf("%d%d",&n,&m);  
    memset(vis,-1,sizeof(vis));  
    for(i=1;i<=n;i++)scanf("%d",&val[i]);  
    for(i=0;i<=n;i++)  
    {  
        node[i].l=node[i].r=0;  
    }  
    for(i=1;i<=n;i++)  
    {  
        int a,b;  
        scanf("%d%d",&a,&b);  
        node[b].r=node[a].l;  
        node[a].l=b;  
    }  
    cout<<dp(node[0].l,m)<<endl;  
}  
int main()  
{  
    init();  
    return 0;  
}  

 

 
 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,