动态规划（dp）基本概念

阳光穿透心脏的1/2处 2022-07-18 16:18 209阅读 0赞

基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

![Center][]

状态抓换方程：

dp\[i\]\[j\] = a\[i\]\[j\] + max(dp\[i+1\]\[j\], dp\[i+1\]\[j+1\]); //dp\[i\]\[j\]表示从(i,j)位置开始走的最大和

代码：

**\[cpp\]** [view plain][] [copy][view plain]

1. \#include<stdio.h>
2. \#include<iostream>
3. \#include<string>
4. \#include<string.h>
5. \#include<algorithm>
6. \#include<vector>
7. \#include<time.h>
8. \#include<queue>
9. \#include<stack>
10. \#include<iterator>
11. \#include<math.h>
12. \#include<stdlib.h>
13. \#include<limits.h>
14. \#include<map>
15. //\#define ONLINE\_JUDGE
16. \#define eps 1e-8
17. \#define INF 0x7fffffff //INT\_MAX
18. \#define inf 0x3f3f3f3f //int范围内可靠的无穷大
19. \#define FOR(i,a) for((i)=0;i<(a);(i)++) //\[i,a);
20. \#define MEM(a) (memset((a),0,sizeof(a)))
21. \#define sfs(a) scanf("%s",a)
22. \#define sf(a) scanf("%d",&a)
23. \#define sfI(a) scanf("%I64d",&a)
24. \#define pf(a) printf("%d\\n",a)
25. \#define pfI(a) printf("%I64d\\n",a)
26. \#define pfs(a) printf("%s\\n",a)
27. \#define sfd(a,b) scanf("%d%d",&a,&b)
28. \#define sft(a,b,c)scanf("%d%d%d",&a,&b,&c)
29. \#define for1(i,a,b) for(int i=(a);i<b;i++)
30. \#define for2(i,a,b) for(int i=(a);i<=b;i++)
31. \#define for3(i,a,b)for(int i=(b);i>=a;i--)
32. \#define MEM1(a) memset(a,0,sizeof(a))
33. \#define MEM2(a) memset(a,-1,sizeof(a))
34. \#define LL \_\_int64
35. **const****double** PI = acos(-1.0); 
36. **template**<**class** T> T gcd(T a, T b) \{ **return** b ? gcd(b, a % b) : a;\} 
37. **template**<**class** T> T lcm(T a, T b) \{ **return** a / gcd(a, b) \* b;\} 
38. **template**<**class** T> **inline** T Min(T a, T b) \{ **return** a **inline** T Max(T a, T b) \{ **return** a > b ? a : b;\} 
40. **using****namespace** std; 
41. **int** n, m; 
42. \#define N 100
43. **int** a\[N\]\[N\]; 
44. **int** dp\[N\]\[N\]; 
45. **void** Into()\{ 
46. sf(n); 
47. memset(dp,-1,**sizeof**(dp)); 
48. **for**(**int** i = 1; i <= n; i++) 
49. **for**(**int** j = 1; j <= i; j++) 
50. sf(a\[i\]\[j\]); 
51. \} 
52. **int** slove(**int** i,**int** j)\{ 
53. **if**(dp\[i\]\[j\] >= 0) 
54. **return** dp\[i\]\[j\]; //记忆化搜索
55. **return** dp\[i\]\[j\] = a\[i\]\[j\] + (i == n ? 0 : Max(slove(i + 1 , j) , slove(i + 1, j + 1))); 
56. \} 
57. **int** main()\{ 
58. \#ifndef ONLINE\_JUDGE
59. freopen("in.txt","r",stdin); 
60. // freopen("out.txt","w",stdout);
61. \#endif
62. **int** t; 
63. sf(t); 
64. **while**(t--)\{ 
65. Into(); 
66. pf(slove(1,1)); 
67. \} 
68. **return** 0; 
69. \}

第二题：HDU 2602（01背包问题）

# Bone Collector #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 38897 Accepted Submission(s): 16122**

Problem Description

Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …  
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?  
![C154-1003-1.jpg][]

Input

The first line contain a integer T , the number of cases. 
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.

Output

One integer per line representing the maximum of the total value (this number will be less than 2 31).

Sample Input

1
    5 10
    1 2 3 4 5
    5 4 3 2 1

Sample Output

题意：

第一行是测试组数t，接下来是n,m分别表示物品总数和背包最大载重，接下来的两行分别是价值和重量。

代码：

**\[cpp\]** [view plain][] [copy][view plain]

1. **for**(**int** j = 0; j <= m; j++)\{ //j表示容量
2. **if**(weight\[i\] <= j)\{ 
3. dp\[i\]\[j\] = Max(dp\[i - 1\]\[j - weight\[i\]\] + value\[i\], dp\[i-1\]\[j\]); //dp\[i\]\[j\]表示装入前i个物体在j体积下的最大价值
4. \} 
5. **else**
6. dp\[i\]\[j\] = dp\[i-1\]\[j\]; 
7. \} 
8. \} 
9. \} 
10. **int** main()\{ 
11. \#ifndef ONLINE\_JUDGE
12. // freopen("in.txt","r",stdin);
13. // freopen("out.txt","w",stdout);
14. \#endif
15. **int** t; 
16. sf(t); 
17. **while**(t--)\{ 
18. Into(); 
19. slove(); //核心步骤
20. pf(dp\[n\]\[m\]); 
21. \} 
22. **return** 0; 
23. \}

还有一道题是易彰彪出的捡死鱼问题：

## **yzb的鱼** ##

时间限制(C/C++):3000MS/6000MS 运行内存限制:65536KByte  
总提交:61 测试通过:13

描述

有一天yzb去澳大利亚，忽然天上掉下鱼。  
说来yzb的人品实在是太好了，鱼别处都不掉，就掉落在他身旁的10米内。yzb马上找来鱼筐去接，而掉在地上的鱼yzb是不会要的。  
但由于yzb运动基因不发达，每秒种只有在移动不超过一米的范围内接住坠落的鱼。  
为了使问题简化，假设在接下来的一段时间里，鱼都掉落在0-10这11个位置。  
开始时yzb站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的鱼。问yzb最多可能接到多少条鱼?

输入

输入数据有多组。每组数据的第一行为以正整数n(0<n<100000)，表示有n条鱼掉在这条小径上。 
在结下来的n行中，每行有两个整数x,T(0<T<100000),表示在第T秒有一条鱼掉在x点上。 
同一秒钟在同一点上可能掉下多个鱼。n=0时输入结束。

输出

每一组输入数据对应一行输出。输出一个整数m，表示yzb最多可能接到m条鱼。

样例输入

6  
5 1  
4 1  
6 1  
7 2  
7 2  
8 3  
0

样例输出

分析：

![Center 1][]

代码：

递归：像我这样的低智商玩家一开始只能想到这个。。。。

**\[cpp\]** [view plain][] [copy][view plain]

1. \#include<stdio.h>
2. \#include<iostream>
3. \#include<string>
4. \#include<string.h>
5. \#include<algorithm>
6. \#include<vector>
7. \#include<time.h>
8. \#include<queue>
9. \#include<stack>
10. \#include<iterator>
11. \#include<math.h>
12. \#include<stdlib.h>
13. \#include<limits.h>
14. \#include<map>
15. //\#define ONLINE\_JUDGE
16. \#define eps 1e-8
17. \#define INF 0x7fffffff //INT\_MAX
18. \#define inf 0x3f3f3f3f //int范围内可靠的无穷大
19. \#define FOR(i,a) for((i)=0;i<(a);(i)++) //\[i,a);
20. \#define MEM(a) (memset((a),0,sizeof(a)))
21. \#define sfs(a) scanf("%s",a)
22. \#define sf(a) scanf("%d",&a)
23. \#define sfI(a) scanf("%I64d",&a)
24. \#define pf(a) printf("%d\\n",a)
25. \#define pfI(a) printf("%I64d\\n",a)
26. \#define pfs(a) printf("%s\\n",a)
27. \#define sfd(a,b) scanf("%d%d",&a,&b)
28. \#define sft(a,b,c)scanf("%d%d%d",&a,&b,&c)
29. \#define for1(i,a,b) for(int i=(a);i<b;i++)
30. \#define for2(i,a,b) for(int i=(a);i<=b;i++)
31. \#define for3(i,a,b)for(int i=(b);i>=a;i--)
32. \#define MEM1(a) memset(a,0,sizeof(a))
33. \#define MEM2(a) memset(a,-1,sizeof(a))
34. \#define LL \_\_int64
35. **const****double** PI = acos(-1.0); 
36. **template**<**class** T> T gcd(T a, T b) \{ **return** b ? gcd(b, a % b) : a;\} 
37. **template**<**class** T> T lcm(T a, T b) \{ **return** a / gcd(a, b) \* b;\} 
38. **template**<**class** T> **inline** T Min(T a, T b) \{ **return** a **inline** T Max(T a, T b) \{ **return** a > b ? a : b;\} 
40. **using****namespace** std; 
41. **int** n, m ,Tm; 
42. \#define N 100010
43. **int** a\[15\]\[N\]; 
44. **int** dp\[15\]\[N\]; 
45. **int** Maxt(**int** a,**int** b,**int** c)\{ 
46. **if**(a>b)\{ 
47. **if**(a>c) 
48. **return** a; 
49. **return** c; 
50. \} 
51. **else****if**(b>c) 
52. **return** b; 
53. **return** c; 
54. \} 
55. **void** Into()\{ 
56. Tm = -inf; 
57. memset(a,0,**sizeof** a); 
58. memset(dp,-1,**sizeof** dp); 
59. **int** p,t; 
60. **for**(**int** i = 0; i < n; i++)\{ 
61. sfd(p,t); 
62. a\[p\]\[t\]++; 
63. Tm = Tm > t ? Tm : t; 
64. \} 
65. \} 
66. **int** slove(**int** i,**int** j)\{ 
67. **if**(dp\[i\]\[j\] >= 0) 
68. **return** dp\[i\]\[j\]; 
69. **if**(j == Tm) 
70. **return** dp\[i\]\[j\] = a\[i\]\[j\]; 
71. **else****if**(i == 10) 
72. **return** dp\[i\]\[j\] = a\[i\]\[j\] + Max(slove( i ,j + 1),slove(i - 1, j + 1)); 
73. **else****if**(!i)\{ 
74. **return** dp\[i\]\[j\] = a\[i\]\[j\] + Max(slove(i + 1,j + 1),slove(i , j + 1)); 
75. \} 
76. **else**
77. **return** dp\[i\]\[j\] = a\[i\]\[j\] + Maxt(slove(i - 1 ,j + 1),slove(i, j + 1),slove(i + 1,j + 1)); 
78. \} 
79. **int** main()\{ 
80. \#ifndef ONLINE\_JUDGE
81. // freopen("in.txt","r",stdin);
82. // freopen("out.txt","w",stdout);
83. \#endif
84. **while**(sf(n)!=EOF && n)\{ 
85. Into(); 
86. pf(slove(5,0)); 
87. \} 
88. **return** 0; 
89. \}

循环：别人优化了一下，自己写了一遍

**\[cpp\]** [view plain][] [copy][view plain]

1. \#include<stdio.h>
2. \#include<iostream>
3. \#include<string>
4. \#include<string.h>
5. \#include<algorithm>
6. \#include<vector>
7. \#include<time.h>
8. \#include<queue>
9. \#include<stack>
10. \#include<iterator>
11. \#include<math.h>
12. \#include<stdlib.h>
13. \#include<limits.h>
14. \#include<map>
15. //\#define ONLINE\_JUDGE
16. \#define eps 1e-8
17. \#define INF 0x7fffffff //INT\_MAX
18. \#define inf 0x3f3f3f3f //int范围内可靠的无穷大
19. \#define FOR(i,a) for((i)=0;i<(a);(i)++) //\[i,a);
20. \#define MEM(a) (memset((a),0,sizeof(a)))
21. \#define sfs(a) scanf("%s",a)
22. \#define sf(a) scanf("%d",&a)
23. \#define sfI(a) scanf("%I64d",&a)
24. \#define pf(a) printf("%d\\n",a)
25. \#define pfI(a) printf("%I64d\\n",a)
26. \#define pfs(a) printf("%s\\n",a)
27. \#define sfd(a,b) scanf("%d%d",&a,&b)
28. \#define sft(a,b,c)scanf("%d%d%d",&a,&b,&c)
29. \#define for1(i,a,b) for(int i=(a);i<b;i++)
30. \#define for2(i,a,b) for(int i=(a);i<=b;i++)
31. \#define for3(i,a,b)for(int i=(b);i>=a;i--)
32. \#define MEM1(a) memset(a,0,sizeof(a))
33. \#define MEM2(a) memset(a,-1,sizeof(a))
34. \#define LL \_\_int64
35. **const****double** PI = acos(-1.0); 
36. **template**<**class** T> T gcd(T a, T b) \{ **return** b ? gcd(b, a % b) : a;\} 
37. **template**<**class** T> T lcm(T a, T b) \{ **return** a / gcd(a, b) \* b;\} 
38. **template**<**class** T> **inline** T Min(T a, T b) \{ **return** a **inline** T Max(T a, T b) \{ **return** a > b ? a : b;\} 
40. **using****namespace** std; 
41. **template**<**class** T> 
42. T Mint(T a,T b,T c)\{ 
43. **if**(a>b)\{ 
44. **if**(c>b) 
45. **return** b; 
46. **return** c; 
47. \} 
48. **if**(c>a) 
49. **return** a; 
50. **return** c; 
51. \} 
52. **template**<**class** T> 
53. T Maxt(T a, T b, T c)\{ 
54. **if**(a>b)\{ 
55. **if**(c>a) 
56. **return** c; 
57. **return** a; 
58. \} 
59. **else****if**(c > b) 
60. **return** c; 
61. **return** b; 
62. \} 
63. **int** n, m ; 
64. \#define N 100010
65. **int** a\[N\]\[15\]; // a\[i\]\[j\] j位置，i时刻能得到的鱼
66. **int** dp\[N\]\[15\]; // dp\[i\]\[j\] j位置，i时间后所获得的最大值
67. **void** slove(**int** Tm)\{ 
68. **for**(**int** i = Tm; i >= 0; i--)\{ 
69. **for**(**int** j = 0; j <= 10 ; j++)\{ 
70. **if**(i == Tm)\{ 
71. dp\[i\]\[j\] = a\[i\]\[j\]; 
72. \} 
73. **else****if**(!j)\{ 
74. dp\[i\]\[j\] = a\[i\]\[j\] + Max(dp\[i+1\]\[j\],dp\[i+1\]\[j+1\]); 
75. \} 
76. **else****if**(j == 10)\{ 
77. dp\[i\]\[j\] = a\[i\]\[j\] + Max(dp\[i+1\]\[j\],dp\[i+1\]\[j-1\]); 
78. \} 
79. **else**\{ 
80. dp\[i\]\[j\] = a\[i\]\[j\] + Maxt(dp\[i+1\]\[j-1\],dp\[i+1\]\[j\],dp\[i+1\]\[j+1\]); 
81. \} 
82. \} 
83. \} 
84. pf(dp\[0\]\[5\]); 
85. \} 
86. **void** Into()\{ 
87. **int** t; 
88. **int** position,time; 
89. **while**(sf(t)!=EOF && t)\{ 
90. **int** Tm = -inf; 
91. memset(dp,0,**sizeof**(dp)); 
92. memset(a,0,**sizeof**(a)); 
93. **while**(t--)\{ 
94. sfd(position,time); 
95. a\[time\]\[position\]++; 
96. Tm = Tm > time ? Tm : time; 
97. \} 
98. slove(Tm); 
99. \} 
100. \} 
101. **int** main()\{ 
102. \#ifndef ONLINE\_JUDGE
103. freopen("in.txt","r",stdin); 
104. // freopen("out.txt","w",stdout);
105. \#endif
106. Into(); 
107. **return** 0; 
108. \}

用循环比用递归快了很多了。

最后一道题，王教授出在oj上的题。

## **最长不降奇偶交替子列** ##

时间限制(C/C++):1000MS/3000MS 运行内存限制:65536KByte  
总提交:227 测试通过:38

描述

一个序列中选择其中的若干个，保持以前顺序生成的新的序列称为原序列的子列，如果子列中每相邻两个元素的奇偶性交替出现，则称这个子列为奇偶交替子列。你的任务是：对于给定的序列， 计算出其最长单调不降奇偶交替子列的长度。

输入

输入的第1行是一个整数n，在\[1, 20\]之间，表示测试用例的数量。对于每一个测试用例， 第一行是一个整数mi，表示该测试用例序列中数据的数量，在\[2, 200\]中。后面紧跟mi行，每一行是该序列的一个数据，每个数据在区间\[-10000, 10000\]之中。

输出

对于每个测试用例，输出一行，只包含一个整数，表示相应测试用例最长不降奇偶交替子列的长度。

样例输入

5  
4  
\-10  
\-5  
\-8  
\-2  
8  
9  
\-7  
\-9  
\-3  
\-13  
\-15  
7  
7  
1  
\-6  
6  
\-17  
\-15  
\-8  
\-2  
\-7  
\-8  
2  
\-7  
0

样例输出

3  
1  
1  
3  
2

分析：想了想自己模拟了一遍画出来大概是棵树的结构，至于是什么树我也不知道，还没学到。

![Center 2][]

字好丑！

代码：

**\[cpp\]** [view plain][] [copy][view plain]

1. \#include<stdio.h>
2. \#include<iostream>
3. \#include<string>
4. \#include<string.h>
5. \#include<algorithm>
6. \#include<vector>
7. \#include<time.h>
8. \#include<queue>
9. \#include<stack>
10. \#include<iterator>
11. \#include<math.h>
12. \#include<stdlib.h>
13. \#include<limits.h>
14. \#include<map>
15. //\#define ONLINE\_JUDGE
16. \#define eps 1e-8
17. \#define INF 0x7fffffff //INT\_MAX
18. \#define inf 0x3f3f3f3f //int范围内可靠的无穷大
19. \#define FOR(i,a) for((i)=0;i<(a);(i)++) //\[i,a);
20. \#define MEM(a) (memset((a),0,sizeof(a)))
21. \#define sfs(a) scanf("%s",a)
22. \#define sf(a) scanf("%d",&a)
23. \#define sfI(a) scanf("%I64d",&a)
24. \#define pf(a) printf("%d\\n",a)
25. \#define pfI(a) printf("%I64d\\n",a)
26. \#define pfs(a) printf("%s\\n",a)
27. \#define sfd(a,b) scanf("%d%d",&a,&b)
28. \#define sft(a,b,c)scanf("%d%d%d",&a,&b,&c)
29. \#define for1(i,a,b) for(int i=(a);i<b;i++)
30. \#define for2(i,a,b) for(int i=(a);i<=b;i++)
31. \#define for3(i,a,b)for(int i=(b);i>=a;i--)
32. \#define MEM1(a) memset(a,0,sizeof(a))
33. \#define MEM2(a) memset(a,-1,sizeof(a))
34. \#define LL \_\_int64
35. **const****double** PI = acos(-1.0); 
36. **template**<**class** T> T gcd(T a, T b) \{ **return** b ? gcd(b, a % b) : a;\} 
37. **template**<**class** T> T lcm(T a, T b) \{ **return** a / gcd(a, b) \* b;\} 
38. **template**<**class** T> **inline** T Min(T a, T b) \{ **return** a **inline** T Max(T a, T b) \{ **return** a > b ? a : b;\} 
40. **using****namespace** std; 
41. **template**<**class** T> 
42. T Mint(T a,T b,T c)\{ 
43. **if**(a>b)\{ 
44. **if**(c>b) 
45. **return** b; 
46. **return** c; 
47. \} 
48. **if**(c>a) 
49. **return** a; 
50. **return** c; 
51. \} 
52. **template**<**class** T> 
53. T Maxt(T a, T b, T c)\{ 
54. **if**(a>b)\{ 
55. **if**(c>a) 
56. **return** c; 
57. **return** a; 
58. \} 
59. **else****if**(c > b) 
60. **return** c; 
61. **return** b; 
62. \} 
63. **int** mod(**int** a)\{ 
64. **return** a % 2 < 0 ? -a % 2 : a % 2; 
65. \} 
66. **int** n, m ; 
67. \#define N 210
68. **int** a\[N\],dp\[N\]; 
69. **void** slove()\{ 
70. dp\[n-1\] = 1; 
71. **for**(**int** i = n - 1; i >= 0; i--)\{ 
72. **for**(**int** j = i + 1; j < n; j++)\{ 
73. **if**(a\[i\] < a\[j\] && mod(a\[i\]) != mod(a\[j\]))\{ 
74. dp\[i\] = Max(dp\[j\] + 1,dp\[i\]); 
75. \} 
76. **else**\{ 
77. dp\[i\] = Max(dp\[i\],1); 
78. \} 
79. \} 
80. \} 
81. **int** max = 0; 
82. **for**(**int** i = 0; i < n; i++) 
83. max = max < dp\[i\] ? dp\[i\] : max; 
84. pf(max); 
85. // pf(dp\[0\]); //dp\[i\]的含义是选了第i项之后形成的最长不降奇偶交替子列的最大长度而不是从第i项开始的最长。。。子列长度
86. // putchar(10);
87. \} 
88. **void** Into()\{ 
89. sf(m); 
90. **while**(m--)\{ 
91. memset(a,0,**sizeof**(a)); 
92. memset(dp,0,**sizeof**(dp)); 
93. sf(n); 
94. for1(i,0,n) 
95. sf(a\[i\]); 
96. slove(); 
97. \} 
98. \} 
99. **int** main()\{ 
100. \#ifndef ONLINE\_JUDGE
101. // freopen("in.txt","r",stdin);
102. // freopen("out.txt","w",stdout);
103. \#endif
104. Into(); 
105. **return** 0; 
106. \}

然后是一道poj上的题目：

Football

<table> 
 <tbody> 
 <tr> 
 <td>Time Limit:&nbsp;1000MS</td> 
 <td>&nbsp;</td> 
 <td>Memory Limit:&nbsp;65536K</td> 
 </tr> 
 <tr> 
 <td>Total Submissions:&nbsp;3780</td> 
 <td>&nbsp;</td> 
 <td>Accepted:&nbsp;1934</td> 
 </tr> 
 </tbody> 
</table>

Description

Consider a single-elimination football tournament involving 2*n* teams, denoted 1, 2, …, 2*n*. In each round of the tournament, all teams still in the tournament are placed in a list in order of increasing index. Then, the first team in the list plays the second team, the third team plays the fourth team, etc. The winners of these matches advance to the next round, and the losers are eliminated. After *n* rounds, only one team remains undefeated; this team is declared the winner.

Given a matrix *P* = \[*pij*\] such that *pij* is the probability that team *i* will beat team *j* in a match determine which team is most likely to win the tournament.

Input

The input test file will contain multiple test cases. Each test case will begin with a single line containing *n* (1 ≤ *n* ≤ 7). The next 2*n* lines each contain 2*n* values; here, the *j*th value on the *i*th line represents *pij*. The matrix *P* will satisfy the constraints that *pij* = 1.0 − *pji* for all *i* ≠ *j*, and *pii* = 0.0 for all *i*. The end-of-file is denoted by a single line containing the number −1. Note that each of the matrix entries in this problem is given as a floating-point value. To avoid precision problems, make sure that you use either the `double` data type instead of `float`.

Output

The output file should contain a single line for each test case indicating the number of the team most likely to win. To prevent floating-point precision issues, it is guaranteed that the difference in win probability for the top two teams will be at least 0.01.

Sample Input

2
    0.0 0.1 0.2 0.3
    0.9 0.0 0.4 0.5
    0.8 0.6 0.0 0.6
    0.7 0.5 0.4 0.0
    -1

Sample Output

Hint

In the test case above, teams 1 and 2 and teams 3 and 4 play against each other in the first round; the winners of each match then play to determine the winner of the tournament. The probability that team 2 wins the tournament in this case is:

<table> 
 <tbody> 
 <tr> 
 <td>P(2 wins)&nbsp;</td> 
 <td>=&nbsp;P(2 beats 1)P(3 beats 4)P(2 beats 3) +&nbsp;P(2 beats 1)P(4 beats 3)P(2 beats 4) =&nbsp;p21p34p23&nbsp;+&nbsp;p21p43p24 = 0.9 · 0.6 · 0.4 + 0.9 · 0.4 · 0.5 = 0.396.</td> 
 </tr> 
 </tbody> 
</table>

The next most likely team to win is team 3, with a 0.372 probability of winning the tournament.

分析：

![Center 3][]

代码：

**\[cpp\]** [view plain][] [copy][view plain]

1. \#include<stdio.h>
2. \#include<iostream>
3. \#include<string>
4. \#include<string.h>
5. \#include<algorithm>
6. \#include<vector>
7. \#include<time.h>
8. \#include<queue>
9. \#include<stack>
10. \#include<iterator>
11. \#include<math.h>
12. \#include<stdlib.h>
13. \#include<map>
14. \#include<set>
15. //\#define ONLINE\_JUDGE
16. \#define eps 1e-8
17. \#define INF 0x7fffffff //INT\_MAX
18. \#define inf 0x3f3f3f3f //int??????????????????
19. \#define FOR(i,a) for((i)=0;i<(a);(i)++) //\[i,a);
20. \#define MEM(a) (memset((a),0,sizeof(a)))
21. \#define sfs(a) scanf("%s",a)
22. \#define sf(a) scanf("%d",&a)
23. \#define sfI(a) scanf("%I64d",&a)
24. \#define pf(a) printf("%d\\n",a)
25. \#define pfI(a) printf("%I64d\\n",a)
26. \#define pfs(a) printf("%s\\n",a)
27. \#define sfd(a,b) scanf("%d%d",&a,&b)
28. \#define sft(a,b,c)scanf("%d%d%d",&a,&b,&c)
29. \#define for1(i,a,b) for(int i=(a);i<b;i++)
30. \#define for2(i,a,b) for(int i=(a);i<=b;i++)
31. \#define for3(i,a,b)for(int i=(b);i>=a;i--)
32. \#define MEM1(a) memset(a,0,sizeof(a))
33. \#define MEM2(a) memset(a,-1,sizeof(a))
34. \#define LL \_\_int64
35. **const****double** PI = acos(-1.0); 
36. **template**<**class** T> T gcd(T a, T b) \{ **return** b ? gcd(b, a % b) : a;\} 
37. **template**<**class** T> T lcm(T a, T b) \{ **return** a / gcd(a, b) \* b;\} 
38. **template**<**class** T> **inline** T Min(T a, T b) \{ **return** a **inline** T Max(T a, T b) \{ **return** a > b ? a : b;\} 
40. **using****namespace** std; 
41. **int** n,m; 
42. \#define N 130
43. **double** team\[N\]\[N\]; 
44. **double** dp\[N\]\[N\]; 
45. **int** sum; 
46. **void** Init() \{ 
47. memset(dp, 0, **sizeof**(dp)); 
48. sum = 1 << n; 
49. **for** (**int** i = 1; i <= sum; i++) \{ 
50. **for** (**int** j = 1; j <= sum; j++) \{ 
51. scanf("%lf", &team\[i\]\[j\]); 
52. \} 
53. \} 
54. \} 
55. **void** compute()\{ 
56. **for**(**int** i = 1; i <= n; i++)\{ 
57. **for**(**int** j = 1; j <= sum; j++)\{ 
58. **if**(i == 1)\{ 
59. **if**(j % 2) 
60. dp\[i\]\[j\] = team\[j\]\[j + 1\]; 
61. **else**
62. dp\[i\]\[j\] = team\[j\]\[j - 1\]; 
63. \} 
64. **else**\{ 
65. **int** flag = ((j - 1) / (1 << (i - 1))) + 1; // 当前队伍的组
66. **for**(**int** k = 1; k <= sum; k++)\{ 
67. **int** temp\_flag = ((k - 1) / (1 << (i - 1))) + 1; // 要比较的队伍的组
68. **if**(flag % 2 && temp\_flag == flag + 1)\{ 
69. dp\[i\]\[j\] += (dp\[i - 1\]\[k\] \* dp\[i - 1\]\[j\] \* team\[j\]\[k\]); 
70. \} 
71. **if**(flag % 2 == 0 && temp\_flag == flag - 1)\{ 
72. dp\[i\]\[j\] += (dp\[i - 1\]\[k\] \* dp\[i - 1\]\[j\] \* team\[j\]\[k\]); 
73. \} 
74. \} 
75. \} 
76. \} 
77. \} 
78. \} 
79. **int** main() \{ 
80. \#ifndef ONLINE\_JUDGE
81. //freopen("in.txt","r",stdin);
82. //freopen("out.txt","w",stdout);
83. \#endif
84. **while** (sf(n) != EOF && n != -1) \{ 
85. Init(); 
86. compute(); 
87. **int** num = 0; **double** p = -1.0; 
88. **for**(**int** i = 1; i <= sum; i++)\{ 
89. **if**(dp\[n\]\[i\] > p)\{ 
90. p = dp\[n\]\[i\]; 
91. num = i; 
92. \} 
93. \} 
94. pf(num); 
95. \} 
96. **return** 0;

1.  \}

出处：http://blog.csdn.net/triose/article/details/47122037

[Center]: /images/20220718/e38879a15e204e11b3d3c13b2f70ad30.png
[view plain]: http://blog.csdn.net/triose/article/details/47122037#
[C154-1003-1.jpg]: /images/20220718/dd35bf9025dd4b7285a28fb9ab4dc134.png
[Center 1]: /images/20220718/3ed062796a294841b719faeca963c100.png
[Center 2]: /images/20220718/33f564d0775642d3afaee09bd4a7abbe.png
[Center 3]: /images/20220718/d9748bbc72c9417680b4d6d19bef127d.png