HDU4089 Activation(어려운 순환 기대 dp)

전송문아아아아아아아아
문제 풀이 사고방식은kuangbin 블로그에서 발췌한 것이다
제목: n명이 줄을 서서 홈페이지에서 게임을 활성화하기를 기다리고 있다.Tomato는 m위에 랭크되어 있다.대열의 첫 번째 사람에 대해한 가지 상황: 1. 활성화에 실패하고 대기열에 남아서 다음 활성화(확률 p1)2를 기다립니다. 연결을 잃고 대기열을 나간 다음에 대기열의 마지막(확률 p2)3, 활성화에 성공하고 대기열(확률 p3)4를 떠나면 서버가 마비되고 서버가 활성화되지 않습니다. 모두 활성화할 수 없습니다.서버 마비 시 Tomato가 대기열에 있는 위치<=k의 확률 구하기
dp[i][j]dp[i][j]dp[i][j]를 정의하여 총 iii개인을 갚기 위해 자신이 jj위에 랭크되어 목표에 도달할 확률
j = = 1 : d p [ i ] [ 1 ] = d p [ i ] [ 1 ] ∗ p 1 + d p [ i ] [ i ] ∗ p 2 + p 4 j==1:dp[i][1]=dp[i][1]*p1+dp[i][i]*p2+p4 j==1:dp[i][1]=dp[i][1]∗p1+dp[i][i]∗p2+p4
1 < j < = k : d p [ i ] [ j ] = d p [ i ] [ j ] ∗ p 1 + d p [ i ] [ j − 1 ] ∗ p 2 + d p [ i − 1 ] [ j − 1 ] ∗ p 3 + p 4 11k < j < = i : d p [ i ] [ j ] = d p [ i ] [ j ] ∗ p 1 + d p [ i ] [ j − 1 ] ∗ p 2 + d p [ i − 1 ] [ j − 1 ] ∗ p 3 kk위의 세 가지 식자화는 각각 얻을 수 있다
j = = 1 : d p [ i ] [ 1 ] = d p [ i ] [ i ] ∗ p 21 + p 41 j==1:dp[i][1]=dp[i][i]*p21+p41 j==1:dp[i][1]=dp[i][i]∗p21+p41
1 < j < = k : d p [ i ] [ j ] = d p [ i ] [ j − 1 ] ∗ p 21 + d p [ i − 1 ] [ j − 1 ] ∗ p 31 + p 41 11k < j < = i : d p [ i ] [ j ] = d p [ i ] [ j − 1 ] ∗ p 21 + d p [ i − 1 ] [ j − 1 ] ∗ p 31 kk이렇게 하면 dp [i] [1, n] dp [i] [1, n] dp [i] [1, n], dp [i−1] [1, n] dp [i-1] [1, n] dp [i−1] [1, n] 이미 상수이다
그래서 특정한 iii에 대해 실제 세 가지 형식은 다시 간소화할 수 있다
j==1:dp[i][1]=dp[i][i]∗p21+모 상수 j=1:dp[i][1]=dp[i][i]*p21+모 상수 j==1:dp[i][1]=dp[i][i][i]=dp[i][i]∗p21+모 상수
1k이렇게 되면 n n 개의 방정식 그룹 n n 개의 미지수이다
우리는 먼저 끝에서 끝까지 dp[i][i]dp[i][i]dp[i]dp[i][i]를 반복해서 풀 수 있다
복잡도는 O(n2)O(n^2)O(n2)

#include 
using namespace std;
const int maxn=2009;
const double eps=1e-7;
int n,m,k;
double dp[maxn][maxn],g[maxn],p1,p2,p3,p4,c[maxn];
int main()
{
	while( cin >> n >> m >> k >> p1 >> p2 >> p3 >> p4 )
	{
		double sumn=0;
		if( p4=1;j--)
			{
				dp[u][i]+=p*c[j];
				p*=p21;
			}
			dp[u][i]/=(1-p);
			dp[u][1]=p21*dp[u][i]+c[1];
			for(int j=2;j