题意:由n个结点组成的树,每个结点有个点权,你从结点1出发,问最多走m步可以获得点权和(重复走一个结点只有第一次走过会
获得点权值)的最大值。
思路:设dp[i][j][k]表示从i结点走j步( k=0表示回到i结点共j步,k=1表示j步之后不回到i节点 )可获得点权和的最大值。
考虑当前的结点u,以及它的子结点v,那么只有三种情况。
(1)dp[u][j + 2][0]=max( dp[u][j + 2][0],dp[u][j - k][0]+ dp[v][k][0] ),即从u向下走了并回到
u共j - k步,接下来又走到v,从v向下走并回到v共k步,再回到u的情况。
(2)dp[u][j + 1][1]=max( dp[u][j + 1][1],dp[u][j - k][0]+ dp[v][k][1] ),即从u向下走并回到u共
j - k步,接下来走到v,并从v向下走k步不回到v的情况。
(3)dp[u][j + 2][1]=max( dp[u][j + 2][1],dp[u][j - k][1]+ dp[v][k][0] ),即从u走到v,并从v向下走
并回到v共k步,再回到u。之后u再向下走j - k步不回到u的情况。
详见代码:
// file name: poj2486.cpp // // author: kereo // // create time: 2014年11月03日 星期一 14时38分35秒 // //***********************************// #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<set> #include<map> #include<vector> #include<stack> #include<cmath> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int sigma_size=26; const int MAXN=200+100; const double eps=1e-8; const int inf=0x3fffffff; const int mod=1000000000+7; #define L(x) (x<<1) #define R(x) (x<<1|1) int n,m,edge_cnt; int dp[MAXN][MAXN][2],num[MAXN],head[MAXN]; struct Edge { int v; int next; }edge[MAXN<<1]; void init(){ edge_cnt=0; memset(dp,0,sizeof(dp)); memset(head,-1,sizeof(head)); } void addedge(int u,int v){ edge[edge_cnt].v=v; edge[edge_cnt].next=head[u]; head[u]=edge_cnt++; } void dfs(int u,int fa){ for(int i=0;i<=m;i++) dp[u][i][0]=dp[u][i][1]=num[u]; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v == fa) continue; dfs(v,u); for(int j=m;j>=0;j--) for(int k=0;k<=j;k++){ dp[u][j+2][0]=max(dp[u][j+2][0],dp[u][j-k][0]+dp[v][k][0]); dp[u][j+1][1]=max(dp[u][j+1][1],dp[u][j-k][0]+dp[v][k][1]); dp[u][j+2][1]=max(dp[u][j+2][1],dp[u][j-k][1]+dp[v][k][0]); } } } int main() { while(~scanf("%d%d",&n,&m)){ init(); for(int i=1;i<=n;i++) scanf("%d",&num[i]); int u,v; for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } dfs(1,-1); printf("%d\n",max(dp[1][m][0],dp[1][m][1])); } return 0; }