【COGS 1489】玩纸牌

题目传送门：http://cogs.top/cogs/problem/problem.php?pid=1489

这一道题真的是坑啊！
总体思路肯定是：先DP出每天完成计划的概率，然后再根据期望的定义来算

然后就是坑点了。
不难得出，转移方程：\(p(i,j) = p(i – 1,j – 1) \cdot {p_{win}} + p(i,j – 1) \cdot {p_{lose}}\)
然而这是错的！因为如果i/j满足条件的话，这个货就会立即停止，即i/j>a/b的概率为0
妈妈啊！wa了好久！

不过这题还是学了一点东西：
1. 枚举的时候，遇到分数，为了避免误差可以变除为乘
2. 全期望公式，不仅可以用来装逼，还可以用来化简式子，避免误差
比如这个题目，使用全期望公式，可以化到：\(ans = \frac{1}{{lose}}\)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

const int MAXN = 1000+9;
const double EPS = 1e-15;

double t1[MAXN],t2[MAXN],win,lose,*p1,*p2;
int n,a,b;

inline double cal(double ty){
	memset(t1,0,sizeof(t1));
	memset(t2,0,sizeof(t2));
	p1 = t1; p2 = t2; p2[0] = 1;
	
	for (int j=1;j<=n;j++) {
		for (int i=0;i*b<=a*j;i++) p1[i] = p2[i]*lose + ((i)?p2[i-1]*win:0);
		swap(p1, p2);
	}
	
	double ret = 0;
	for(int i=0;i*b<=a*n;i++) ret += p2[i];
	return ret;
}

int main(){
    freopen("expected.in","r",stdin);
    freopen("expected.out","w",stdout);
	int TT; cin>>TT;
	for (int T=1;T<=TT;T++){
		scanf("%d/%d %d",&a,&b,&n);
		win = (double)a/b; lose = 1-win;
		lose = cal(win); win = 1.0 - lose;
		double  w = 1, vout = 0; int day = 1;
		while (w > EPS) {
			vout += w*lose*day;
			w *= win; day++;
		}
		printf("Case #%d: %d\n",T,(int)(vout+0.05));
	}
	return 0;
}