题意：给你 两种泡面 N包，然后你扔硬币，正面朝上吃第一种，反面呢 吃第二种，有任意一种吃完时 就不需要跑硬币了，求停止抛硬币的 期望，
这题目做出来具有运气成分，
首先想了很久，题目暴力肯定不行，我想先对 概率进行DP，然后乘以次数得到期望，但是想了很久不行
我对第二个案例进行了 分析，也就是N=2的时候，首先 可以想得到在合理的 DP方程肯定 最基础的形态 肯定是 DP[I][J] = DP[I-1][J] / 2+ DP[]I[J-1] / 2……，因为每次都是两种选一个嘛，然后 当N等于2的 时候 DP[2][2] = DP[1][2] + DP[2][1], DP[2][1] = DP[1][1] + DP[2][0],另一个 DP[1][2]也是相同的 继续 对DP[1][1] = DP[1][0] + DP[0][1]，推到这里我们可以大胆的猜测DP[I][0] 和DP[0][I] 肯定是边界，至于 值是 多少我们可以看到 题目第一个案例 也就是N为1的时候，期望为1，我想对期望直接进行DP， 那么 DP[1][1] = 1.00，那么 DP[1][1] = DP[1][0] + DP[0][1],这里赋值边界，一般只能赋值0，那么如何让DP[1][1] = 1?直接后面加一个1？ 于是大胆的试了一下 发现 把状态转移方程 写成
DP[I][J] = DP[I-1][J] / 2+ DP[]I[J-1] / 2 + 1,后来发现DP[2][2]的值 刚好正确， 但是是不是巧合呢 于是 就利用暴力程序来跑案例 ，这个暴力程序是可以输出 两种泡面任意剩余量 时的 期望值 ，也就是 对应我的DP方程的 DP[I][J]的值， 最后跑了很多案例 前几个都对 后面小数位第二位有区别，一开始 不敢确定是精度误差导致的，犹豫了一会 后来交了一把
发现超时，那么就开心了，最起码 没有WA，然后看了一下，题目还有一个输入值是 案例数T，题目最大 时间应该是 T*N*N，所以 要把 N*N的这个程序 放在外面 进行预处理，到时候 N为多少 直接输出 DP[N][N]即可
总是做算法，不如来个陶冶情操的文章一篇： http://www.sanwen.net/subject/3628849/
#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#define ll long long
#define eps 1e-8
//const ll INF = 1ll<<61;
using namespace std;
//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;
/*
int main() {//暴力验证程序
int n, m;
while(~scanf("%d %d",&n,&m)){
int zz = 0, T= 500000;
for(int i = 0; i < T; i++){
int a = n, b = m;
int ans = 0;
while(a&&b){
int k = rand()&1;
if(k)a--;
else b--;
ans++;
}
zz += ans;
}
printf("%.2lf\n",((double)zz/(double)T));
//printf("%d/%d\n",zz,T);
puts("");
}
return 0;
}
/*
1 1
1 2
2 1
2 2
3 3
4 4
5 5
6 6
7 7
17 17
ans :
1.00
1.50
2.50
4.13
5.81
7.53
9.28
*/
double dp[1000 + 5][1000 + 5];
void clear() {
memset(dp,0.00,sizeof(dp));
for(int i=0;i<=1000;i++) {/*边界*/
for(int j=0;j<=1000;j++) {
dp[i][0] = 0.00;
dp[0][j] = 0.00;
}
}
}
void init() {
for(int i=1;i<=1000;i++) {
for(int j=1;j<=1000;j++) {
dp[i][j] = dp[i-1][j] * 0.5 + dp[i][j-1] * 0.5 + 1.00;
}
}
}
int main() {
int t;
init();
scanf("%d",&t);
while(t--) {
int n;
scanf("%d",&n);
printf("%.2lf\n",dp[n][n]);
}
return 0;
}
/*
100
1
2
3
4
5
6
7
8
9
10
11
17
*/ZOJ 2949 Coins of Luck 概率DP,布布扣,bubuko.com
原文：http://blog.csdn.net/yitiaodacaidog/article/details/22605321