發表新討論
#21594: 樹dp


yyyykcccc (yyyykcccc)

學校 : 不指定學校
編號 : 121261
來源 : [220.136.159.80]
最後登入時間 ：
2020-06-25 23:38:06
a265. 紅黑樹 -- 2011成功高中校內賽複賽第一題 | From: [140.113.123.230] | 發表日期 : 2020-06-25 14:50
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<vector>
  6. using namespace std;
  7. const int MAXN = 300;
  8. const int MAXL = 40;
  9.  
  10. int n;
  11. int out[MAXN], in[MAXN];
  12. vector<int> G[MAXN];
  13. int dp[MAXN][2][MAXN];
  14.  
  15. // r: 0, b: 1
  16. #define C_B 1
  17. #define C_R 0
  18.  
  19. int error = 0;
  20.  
  21. void dfs(int u, int mi, int mx) {
  22. if (u < mi || u > mx) {
  23. error = 1;
  24. }
  25. if (G[u].size() == 0) { // leaf node
  26. dp[u][C_B][1] = 1;
  27. dp[u][C_R][0] = 1;
  28. } else if (G[u].size() == 1) { // one children
  29. int v = G[u][0];
  30. dfs(v, mi, mx);
  31. // u color C_B: child can be C_B or C_R, and only one black
  32. dp[u][C_B][1] = max(dp[v][C_R][0], dp[v][C_B][0]);
  33. // u color C_R: no possible for C_B
  34. } else if (G[u].size() == 2) { // two children
  35. int v = G[u][0];
  36. int w = G[u][1];
  37. if (v > w) swap(v, w);
  38.  
  39. dfs(v, mi, min(mx, u));
  40. dfs(w, max(mi, u), mx);
  41.  
  42. // u color C_B: children can be black or red
  43. for (int i = 0; i < MAXL; i++) {
  44. dp[u][C_B][i + 1] = max(dp[u][C_B][i + 1], dp[v][C_B][i] * dp[w][C_B][i] +
  45. dp[v][C_R][i] * dp[w][C_B][i] +
  46. dp[v][C_B][i] * dp[w][C_R][i] +
  47. dp[v][C_R][i] * dp[w][C_R][i]); // RR
  48. }
  49.  
  50. // u color C_R: children can only be both black
  51. for (int i = 0; i < MAXL; i++) {
  52. dp[u][C_R][i] = max(dp[u][C_R][i], dp[v][C_B][i] * dp[w][C_B][i]);
  53. }
  54. }
  55. }
  56.  
  57. int main() {
  58. int kase = 1;
  59. while (cin >> n) {
  60. error = 0;
  61. memset(out, 0, sizeof(out));
  62. memset(in, 0, sizeof(in));
  63. memset(dp, 0, sizeof(dp));
  64. for (int i = 0 ; i < MAXN; i++) {
  65. G[i].clear();
  66. }
  67. for (int i = 0; i < n-1; i++) {
  68. int u, v;
  69. cin >> u >> v;
  70. G[u+100].push_back(v+100);
  71. in[v+100]++;
  72. out[u+100]++;
  73. }
  74.  
  75. int root = 0;
  76. for (int i = 0 ; i < MAXN; i++) {
  77. if (in[i] == 0 && out[i] > 0) {
  78. root = i;
  79. }
  80. }
  81.  
  82. dfs(root, -100000, 100000);
  83.  
  84. int ret = 0;
  85. for (int i = 0; i < MAXL; i++) {
  86. ret += dp[root][C_B][i];
  87. }
  88. if (error) ret = 0;
  89. printf("Case %d:%d\n", kase++, ret);
  90. }
  91. return 0;
  92. }
 
ZeroJudge Forum