[CodeVS 1378]选课

danihao123 posted @ 2016年9月16日 19:52 in 题解 with tags CodeVS CTSC 动态规划 背包DP 树形DP 左儿子右兄弟法 , 199 阅读
转载请注明出处:http://danihao123.is-programmer.com/

上古CTSC提……竟然只是树形背包DP……

树形背包DP可以使用左儿子右兄弟法进行优化。这样的话每个点只需要考虑要选不选自己,摊派给兄弟多少,摊派给儿子多少。不过至于这样为何有很大的优化效果,可以参考完全背包的优化方法进行理解。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=305;
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int lc[maxn],rb[maxn],W[maxn];
inline void Insert(int x,int y,int w){
    rb[y]=lc[x];
    lc[x]=y;
    W[y]=w;
}

int d[maxn][maxn];
int dp(int x,int k){
    if(x==-1 || k<=0)
        return 0;
    if(d[x][k]>=0)
        return d[x][k];
    int i;
    int& ans=d[x][k];
    ans=dp(rb[x],k);
    for(i=0;i<k;i++){
        ans=max(ans,W[x]+dp(lc[x],i)+dp(rb[x],k-i-1));
    }
    return ans;
}

int main(){
    register int i;
    int n,m,x,w;
    scanf("%d%d",&n,&m);
    CL_ARR(lc,-1);
    CL_ARR(rb,-1);
    for(i=1;i<=n;i++){
        scanf("%d%d",&x,&w);
        Insert(x,i,w);
    }
    CL_ARR(d,-1);
    printf("%d\n",dp(0,m+1));
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter