题目大意：每个人一个分数，输入几组上下级关系的数据a、b，b是a的上级，然后约束条件是一场宴会中不能存在上下级的两个人或以上，但上级的上级不算，然后把所有人的分数相加，找到最大值，当然这里不是人越多分数越高，有可能存在一个人比所有人分数要高的情况
解题思路：第一题树形DP题，本题是看前辈们的题解写得。总的来说就是还是动态规划的那几步，拆分问题就是每次判断两个人是否为上下级关系，如果上级来了，下级一定不来；如果上级不来，下级有两种情况：来or不来。状态：我们用dp[i][0]表示i这个人不来的情况，从他到他的所有下级的分数累和最大值。同样的，dp[i][1]就表示他来得情况。转移方程：dp[i][1]+=dp[son[j]][0](son-->i的下级，j=0,1,2...),dp[i][1]+=max(dp[son[j]][1],dp[son[j]][1])。这里我觉得难点在构造这个树的关系，网上方法有很多，暂时写了这种方法
//这个方法耗时太大poj2342能过，hdu1520过不了
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int max(int a,int b)
{
return a>b?a:b;
}
int dp[6010][2],n,cas[6010],vis[6010],s[6010];
void tree_dfs(int father)
{
s[father]=1;
dp[father][1]=cas[father];
for(int i=1;i<=n;i++)
{
if(!s[i] && vis[i]==father)
{
tree_dfs(i);
dp[father][1]+=dp[i][0];
dp[father][0]+=max(dp[i][1],dp[i][0]);
}
}
}
int main()
{
int i,father,a,b;
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
scanf("%d",&cas[i]);
memset(dp,0,sizeof(dp));
memset(s,0,sizeof(s));
memset(vis,0,sizeof(vis));
father=0;
while(scanf("%d%d",&a,&b) && (a+b))
vis[a]=b,father=a;
while(vis[father])
father=vis[father];
// printf("%d\n",father);
tree_dfs(father);
printf("%d\n",max(dp[father][1],dp[father][0]));
}
return 0;
}#include<stdio.h>
#include<string.h>
#define MAX_N 6010
struct node
{
int father,son;
int next;
}point[MAX_N];
int dp[MAX_N][2],n,value[MAX_N],list[MAX_N],ls,s[MAX_N]; //list-->为静态链表的每一个位置标号
void with(int father1,int son1)
{
point[ls].father=father1;
point[ls].son=son1;
point[ls].next=list[father1]; //next-->指向兄弟结点 list-->存同一个父亲即兄弟(并且是最后出现的那个兄弟),指向上一个已存在的兄弟的链表模块中
list[father1]=ls++;
return ;
}
int max(int a,int b)
{
return a>b?a:b;
}
void tree_dfs(int f)
{
if(!list[f]) //如果这个父亲结点位置没有更新过 说明到末结点
{
dp[f][1]=value[f];
dp[f][0]=0;
return ;
}
int now=list[f]; //把父节点位置的链表标号给now
dp[f][0]=0;
dp[f][1]=value[f];
while(now) //找出所有兄弟位置的和的最大值
{
tree_dfs(point[now].son);
dp[f][1]+=dp[point[now].son][0];
dp[f][0]+=max(dp[point[now].son][0],dp[point[now].son][1]);
now=point[now].next; //找他的兄弟
}
return ;
}
int main()
{
int i,a,b,t;
int flag[MAX_N];
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
scanf("%d",&value[i]);
memset(list,0,sizeof(list));
// memset(s,0,sizeof(s));
memset(flag,0,sizeof(flag));
t=1;
ls=1;
while(scanf("%d%d",&a,&b) && a+b)
{
with(b,a);
// s[a]=t=b;
flag[a]=1;
}
/*
while(s[t])
t=s[t];
*/
//两种找祖先的方法耗时一致
while(flag[t])
t++;
tree_dfs(t);
printf("%d\n",max(dp[t][1],dp[t][0]));
}
return 0;
}这题卡了挺久的原因在于那个ls，point相当于一个每一个表，而ls则是给他标号，最后那句是list[father1]=ls++;而不是++ls,并且这句可以让父亲结点指向最小儿子结点，即如果有多个儿子的情况下，这个指针一定是指向那个儿子链表的头
京公网安备 11010502036488号