TCO round 1C的 250 和500 的题目都太脑残了，不说了。
TCO round 1C 950 一个棋子，每次等概率的向左向右移动，然后走n步之后，期望cover的区域大小？求cover，肯定就是dp[l][r][n], 走了n步之后，左边cover了l，右边cover了r。
一开始DP没有搞清楚，这个要画一下图就更清楚了。 转移方程就是概率的传递方向.
1: double dp[505][505][2]; // l,r,n steps unsed;
2: class RedPaint
3: {
4: public:
5: double expectedCells(int N)
6: {
7: memset(dp,0,sizeof(dp));
8: // the probability of the configuration.
9: dp[0][0][0] = 1.0;
10: dp[0][1][1] = 0.5;
11: dp[1][0][1] = 0.5;
12: for(int n = 2; n<N+1; n++)
13: {
14: for(int i=0; i<N+1; i++) for(int j=0; j<N+1; j++) dp[i][j][n&1] = 0;
15: for(int l= 0; l<N+1; l++)
16: {
17: for(int r = 0; r<N+1; r++)
18: {
19: if(l== r && r == 0 ) continue;
20: if( l == 0) dp[l][r][n&1] = (dp[0][r-1][(n-1)&1] + dp[1][r-1][(n-1)&1]) * 0.5;
21: else if(r == 0) dp[l][r][n&1] = (dp[l-1][r][(n-1)&1] + dp[l-1][r+1][(n-1)&1]) * 0.5;
22: else
23: dp[l][r][n&1] = (dp[max(0,l-1)][r+1][(n-1)&1] + dp[l+1][max(r-1,0)][(n-1)&1]) * 0.5;
24: }
25: }
26: }
27: double ret = 0.0f;
28: double pro = 0.0f;
29: for(int l=0; l<N+1; l++)
30: {
31: for(int r = 0; r<N+1; r++)
32: {
33: pro += dp[l][r][N&1];
34: cout<<l<<" "<<r<<" "<<N<<" "<<dp[l][r][N&1]<<endl;
35: ret += (l+r+1) * dp[l][r][N&1];
36: }
37: }
38: cout<<"All Pro "<<pro<<endl;
39: return ret;
40: }
41: };
.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }