概率DP
kuangbin总结中的第5题
题解copy：
HDU 4098
题意：有n个人排队等着在官网上激活游戏。Tomato排在第m个。
对于队列中的第一个人。有一下情况：
1、激活失败，留在队列中等待下一次激活（概率为p1)
2、失去连接，出队列，然后排在队列的最后（概率为p2）
3、激活成功，离开队列（概率为p3）
4、服务器瘫痪，服务器停止激活，所有人都无法激活了。
求服务器瘫痪时Tomato在队列中的位置<=k的概率 解析：
概率DP；
设dp[i][j]表示i个人排队,Tomato排在第j个位置，达到目标状态的概率(j<=i)
dp[n][m]就是所求
j==1: dp[i][1]=p1*dp[i][1]+p2*dp[i][i]+p4;
2<=j<=k: dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4;
k<j<=i: dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1];
化简：
j==1: dp[i][1]=p*dp[i][i]+p41;
2<=j<=k: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1]+p41;
k<j<=i: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1]; 其中:
p=p2/(1-p1);
p31=p3/(1-p1)
p41=p4/(1-p1) 可以循环i=1->n 递推求解dp[i].在求解dp[i]的时候dp[i-1]就相当于常数了。
在求解dp[i][1~i]时等到下列i个方程
j==1: dp[i][1]=p*dp[i][i]+c[1];
2<=j<=k:dp[i][j]=p*dp[i][j-1]+c[j];
k<j=i: dp[i][j]=p*dp[i][j]+c[j];
其中c[j]都是常数了。上述方程可以解出dp[i]了。
首先是迭代得到 dp[i][i].然后再代入就可以得到所有的dp[i]了。 注意特判一种情况。就是p4<eps时候，就不会崩溃了，应该直接输出0
*/
啊……那个迭代一开始没有看懂……后来自己写了一下：
f(i,1)=f(i,i)*p+c[1]
f(i,2)=f(i,1)*p+c[2]
……
f(i,i)=f(i,i-1)*p+c[i]
将前 i -1个式子依次代入第 i 个式子中可得：
f(i,i)=……[( f(i,i)*p+c[1])*p + c[2] ]*p +c[3] ……
（就是f(i,i)*p再加c[1]，再*p，+c[2]，再*p，+c[3]……（秦九韶算法？）
完全展开后得到：
f(i,i)=f(i,i)*p^i+c[1]*p^(i-1)+……
就可以算出来f(i,i)了……
//HDOJ 4089
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,INF=~0u>>;
const double eps=1e-;
/*******************template********************/ double f[N][N],pp[N],c[N];
int main(){
// freopen("input.txt","r",stdin);
int n,m,k;
double p1,p2,p3,p4;
while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)!=EOF){
if (p4<eps){
printf("0.00000\n");
continue;
}
double p=p2/(-p1),
p41=p4/(-p1),
p31=p3/(-p1);
pp[]=1.0;
F(i,,n) pp[i]=p*pp[i-]; f[][]=p41/(-p);
c[]=p41;
F(i,,n){
F(j,,k) c[j]=p31*f[i-][j-]+p41;
F(j,k+,i) c[j]=p31*f[i-][j-];
double tmp=c[]*pp[i-];
F(j,,i) tmp+=c[j]*pp[i-j];
f[i][i]=tmp/(-pp[i]);
f[i][]=p*f[i][i]+c[];
F(j,,i-) f[i][j]=p*f[i][j-]+c[j];
}
printf("%.5lf\n",f[n][m]);
}
return ;
}