[CodeVS 1378]选课

上古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;
}

[CodeVS 1380]没有上司的舞会

树形DP处女作……

刚开始各种蜜汁错误……后来发现dp函数竟然忘写返回值……so sad

代码:

#include <cstdio>
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
const int maxn=6001;
vector<int> G[maxn];
void Add_Edge(int x,int y){
	G[x].push_back(y);
}

int d[maxn][2],R[maxn];
int dp(int x,int y,int fa){
	if(d[x][y]!=-0x5ffffff)
		return d[x][y];
	int i,temp;
	if(y==1){
		d[x][y]=R[x];
		for(i=0;i<G[x].size();i++){
			temp=G[x][i];
			if(temp!=fa)
				d[x][y]+=dp(temp,0,x);
		}
	}else{
		d[x][y]=0;
		for(i=0;i<G[x].size();i++){
			temp=G[x][i];
			if(temp!=fa)
				d[x][y]+=max(dp(temp,0,x),dp(temp,1,x));
		}
	}
	return d[x][y];
}

int main(){
	int n,u,v;
	register int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&R[i]);
	for(i=1;i<=n-1;i++){
		scanf("%d%d",&u,&v);
		Add_Edge(u,v);
		Add_Edge(v,u);
	}
	for(i=0;i<=n;i++)
		d[i][0]=d[i][1]=-0x5ffffff;
	printf("%d\n",max(dp(1,0,0),dp(1,1,0)));
	return 0;
}