树形动态规划 fjutoj-2392 聚会的快乐
聚会的快乐
TimeLimit:1000MS MemoryLimit:128MB
64-bit integer IO format: %lld
Problem Description
你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快，尽可能多地找些有趣的热闹。但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。给定N个人（姓名，他幽默的系数，以及他上司的名字），编程找到能使幽默系数和最大的若干个人。
Input
第一行一个整数N（N<100）。接下来有N行，每一行描述一个人的信息，信息之间用空格隔开。姓名是长度不超过20的字符串，幽默系数是在0到100之间的整数。
Output
所邀请的人最大的幽默系数和。
SampleInput
5 BART 1 HOMER HOMER 2 MONTGOMERY MONTGOMERY 1 NOBODY LISA 3 HOMER SMITHERS 4 MONTGOMERY
SampleOutput
8
思路 先建树，深搜遍历，再回溯时 进行状态转移
dp[now][0] =dp[now][0]+max(dp[to][0],dp[to][1]); //0不放,1放 now为当前节点，to为子节点
dp[now][1] =dp[now][1]+dp[to][0]; //当前节点为1时，子节点一定不能有，当前节点为0时，子节点可有可无
最后输出dp[1][0],dp[1][1]中的较小值
下面附上代码
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<vector> 5 #include<algorithm> 6 using namespace std; 7 char s[105][30]; 8 vector<int>e[105]; 9 int v[105]; 10 int dp[105][2]; 11 int tot=0; 12 int vis[105]; 13 void dfs(int now) 14 { 15 int len = e[now].size(); 16 for(int i=0; i<len; i++) 17 { 18 int to = e[now][i]; 19 if(!vis[to]) 20 { 21 vis[to]=1; 22 dfs(to); 23 } 24 } 25 for(int i=0; i<len; i++) 26 { 27 int to = e[now][i]; 28 dp[now][0] =dp[now][0]+max(dp[to][0],dp[to][1]); //0不放,1放 29 dp[now][1] =dp[now][1]+dp[to][0]; 30 } 31 dp[now][1]+=v[now]; 32 } 33 34 int main() 35 { 36 char str[30]; 37 char ttr[30]; 38 int n; 39 scanf("%d",&n); 40 for(int i=0; i<n; i++) 41 { 42 int value,f1=0,f2=0,from,to; 43 scanf("%s%d%s",str,&value,ttr); 44 for(int j=0; j<tot; j++) 45 { 46 if(!strcmp(str,s[j])) 47 { 48 from = j+1; 49 f1=1; 50 } 51 else if(!strcmp(ttr,s[j])) 52 { 53 to = j+1; 54 f2=1; 55 } 56 } 57 if(f1==0) 58 { 59 strcpy(s[tot],str); 60 tot++; 61 from = tot; 62 } 63 if(f2==0) 64 { 65 strcpy(s[tot],ttr); 66 tot++; 67 to = tot; 68 } 69 e[from].push_back(to); 70 e[to].push_back(from); 71 v[from] = value; 72 73 } 74 vis[1]=1; 75 dfs(1); 76 printf("%d\n",max(dp[1][0],dp[1][1])); 77 return 0; 78 }
查看45道真题和解析
