POJ 1155 树形背包(DP) TELE

题目链接:  POJ 1155 TELE

分析:  用dp[i][j]表示在结点i下最j个用户公司的收益, 做为背包处理.

       dp[cnt][i+j] = max( dp[cnt][i+j] , dp[cnt][i]+dp[son][j]-pay );

      其中pay是cnt->son这一路径的成本

代码: 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0x7FFFFFFF;
const int maxn = 3005; struct node{
int to;
int pay;
node* next;
}tree[maxn],*head[maxn]; int w[maxn],num[maxn],tmp[maxn];
int dp[maxn][maxn];
int n,m,ptr; void Init(){
ptr=1;
memset(num,0,sizeof(num));
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
dp[i][j]=-inf;
} void AddEdge(int a,int b,int c){
tree[ptr].to=b;
tree[ptr].pay=c;
tree[ptr].next=head[a];
head[a]=&tree[ptr++];
} void DFS(int cnt){
dp[cnt][0]=0;
if(cnt>n-m){
num[cnt]=1;
dp[cnt][1]=w[cnt];
return ;
}
node* p=head[cnt];
while(p!=NULL){
DFS(p->to);
for(int i=0;i<=num[cnt];++i)
tmp[i]=dp[cnt][i]; ///不能放到下面的循环里, 因为可能有些会改变
for(int i=0;i<=num[cnt];++i)
for(int j=1;j<=num[p->to];++j)
dp[cnt][i+j]=max(dp[cnt][i+j],tmp[i]+dp[p->to][j]-p->pay);
num[cnt]+=num[p->to]; ///cnt的子结点最多能选用户的数量
p=p->next;
}
} int main(){
while(~scanf("%d%d",&n,&m)){
Init();
for(int i=1;i<=n-m;++i){
int t; scanf("%d",&t);
while(t--){
int a,b; scanf("%d%d",&a,&b);
AddEdge(i,a,b);
}
}
for(int i=n-m+1;i<=n;++i)
scanf("%d",w+i);
DFS(1);
for(int i=m; i>=0; --i)
if(dp[1][i]>=0) {
printf("%d\n",i); break;
}
}
return 0;
}
上一篇:ffmpeg 增加视频流媒体质量评估滤镜 (Video Multimethod Assessment Fusion, VMAF)


下一篇:mysql基本介绍和优化技巧