[정수리] [DP 확률 DP 앨범] [10, 4 최신 업데이트]

11124 단어
대학에 입학한 후에 자신이 확률 문제에 대해 매우 감기에 걸리지 않는다는 것을 알게 되었는데, 사실은 줄곧 이랬다. 고등학교는 수학을 제대로 공부하지 못했다.확률이 좋지 않은 결과는 확률류 dp에 대해just soso를 파악한 것이다. 왜냐하면 이런 dp의 상태와 이동에 민감하지 않기 때문이다. yy이거나 상태를 오래 생각하고 이동하려고 하기 때문이다.
지금은 한동안 자신을 학대하고 확률 dp를 하기로 마음먹었다.
    Codeforces 148D Bag of mice  
상태 이동 방정식은 생각하기 어렵다. 가상 경기를 할 때 50분을 썼는데 AC가 없다. win[i][j]를 설정하면 공주가 이길 확률을 표시하고lost[i][j]는 용이 질 확률을 표시한 다음에 제목에 따라 이동한다.상태 전환 방정식은 다음과 같습니다.
    win[i][j] = i * 1.0/(i + j);//i마리 흰쥐 j마리 검은 쥐 시 공주는 흰쥐 win[i][j]+=lost[i][j-1]*j*1.0/(i+j);//i 흰 쥐 j마리 검은 쥐 때 공주는 검은 쥐를 선택했지만 공주가 검은 쥐를 선택한 후 용은 로스트[i][j]=j*1.0/(i+j)*win[i-1][j-1]*(i*1.0/(i+j-1))에게 졌다.//i마리 흰쥐 j마리 검은쥐를 선택할 때 용은 검은쥐를 선택하고 선택한 후 뛰어내려 흰쥐를 잡는다lost[i][j]+=j*1.0/(i+j)*win[i][j-2]*(((j-1)*1.0/(i+j-1)))).//i 흰쥐 j마리 검은쥐 때 용은 검은쥐, 고르고 뛰쳐나가면 검은쥐
     
     Sgu 495 Kids and Prizes  
비교적 간단한 확률 DP.m 개인은 n개의 선물을 선택하고 선택의 기대를 물어본다.모든 사람이 선물을 선택하는 것은 독립적이기 때문에 추측 구해 과정 n은 단지 확률을 구하는 데 쓰일 뿐이다.dp[i]를 설정하면 i개인이 선물을 선택할 확률을 표시하고, np[i]는 i개인이 선물을 선택하지 않을 확률을 나타낸다.그러면 dp[i] = dp[i-1] * np[i-1] + dp[i-1] *(dp[i-1] -1.0/n), 만약 이전 사람이 뽑히지 않았다면 이번 뽑을 확률은 지난번 뽑을 확률과 마찬가지로 dp[i-1]이고 만약에 지난번에 뽑혔으면 이번 뽑을 확률은 dp[i-1] -1.0/n이다.np[i]=1-dp[i];이런 방법의 복잡도는 O(m)이지만 사실은 O(1)면 된다.반대로 뽑히지 않을 기대를 구하면 답은 n-n*((n-1)/n)^m입니다. 선물마다 m 개인이 뽑히지 않을 확률은 (n-1)/n)^m입니다. 선물마다 똑같기 때문에 n을 곱하면 OK입니다.
     Zoj 3383 Patchouli's Spell Cards
확률 DP, m 위치 선택, 각 채우는 수의 범위는 1...n, 적어도 l개의 수가 같은 확률이 있는지 물어본다.반대로 고려하면 l개의 같은 수가 나타나지 않는 확률 p를 구하면 1-p가 답이다.모델이 바뀌면 DP를 진행할 수 있습니다. dp[i][j]를 설정하면 i번째 수로 j개의 위치를 채운 방안 수를 표시합니다. 그러면 dp[i][j]=dp[i-1][j-k]+C[m-(j-k)][k](k     Zoj 3460 Help Me Escape 
저장(浙江)성 대월경기의 제목은 시합할 때 방법을 생각해 냈지만 문자열 한 문제에 걸려서 칠 겨를이 없었다.제목의 대략적인 뜻은 한 마리의 뱀파이어가 매번 랜덤으로 n개 동굴 중 임의의 하나를 선택한다. 만약에 이 뱀파이어의 공격치가 이 동굴ci보다 크면 바로 Ti의 시간을 들여 나갈 수 있다. 그렇지 않으면 하루를 분투해야 한다. 이 뱀파이어의 공격치가 증가하면ci를 랜덤으로 n개 동굴을 선택해야 한다.구설 dp[i]는 공격력이 i일 때 도망가려는 기대를 나타낸다. 그러면 상태 이동 방정식은 dp[i]=sum(wi)/n이고,ci=i일 때wi=1+dp[i+ci]이다.역순으로 상태 이동을 할 수도 있고 기억화 검색을 할 수도 있어 기억화 검색이 이해하기 쉽다.
     Hdu 4405 Aeroplane chess 
위치 0에서 시작하여 한 걸음에 1,2,3,4,5,6개의 위치를 랜덤으로 걷는다. n의 위치와 같은 기대 걸음수를 묻는다. 그리고 일부 위치는 제한이 있다. 일부 xi는 yi에 대응하고 xi에 도착하면 반드시 yi에 도착해야 한다는 뜻이다. 한 걸음도 아니다.이전 문제와 비슷하고 좀 더 간단하지만,
간단하게 생각해 보는 방법은 dp[i]가 i에 도달했을 때의 기대를 표시하고 p[i]가 i에 도달했을 때의 확률을 표시하면 dp[i]+=(dp[j]+p[j])*1/6.0, p[i]+=p[j]*1/6.0, (j에서 i로)next[i]!i시 dp[i]=dp[j],p[i]=p[j];마지막 답은 dp[n];이 공식은 이렇게 유도된 것이다. dp[j]=day*p를 가정하면 dp[i]=(day+1)*p*1/6.0, 즉 dp[i]=(dp[j]+p[j])*1/6.0.
풀면 dp[i]는 i 위치에 도달하는 기대 일수를 나타낸다.dp[i] = dp[j] (next[i] == i), dp[i] += (dp[j] + 1) * 1/6.0.
     Hdu 4336 Card Collector 
상태는 DP를 압축해서 풀고 dp[i]는 i가 최종 상태까지 원하는 카드 수를 나타낸다. dp[i]=dp[i]*myself+sum(dp[j]*p[k]=sum(dp[j]*p[k])/(1-myself)(i|k=j 및 i!=j,myself는 원형을 유지할 확률을 표시한다).
이 문제는 사실 내가 YY에서 용척 원리를 사용한 것이다. 테스트 데이터를 보면 2^n으로 매거할 수 있는 것과 비슷하다. 그리고 매거한 카드의 확률을 합쳐서 기대를 계산하고 홀수와 짝수를 줄인 다음에 지나간다.용척의 원리를 왜 사용할 수 있는지 생각한 후에 믿을 만한 설명을 찾아 자기 위안을 찾았다. E1은 1을 사려는 기대를 나타낸다. E1=1/p1이다. 즉, E1 가방에 1이라는 카드가 포함되어 있다는 것이다. 우리가 E1과 E2를 계산할 때 우리가 카드 1을 원할 때 이미 카드 2를 샀고 그 다음에 우리는 카드 2를 사려는 기대를 계산해야 한다. 바로 이런 교집합으로 우리는 용척을 사용할 수 있기 때문이다.교집합의 기대 E12=1/(p1+p2)는 1,2중 1팩을 무조건 산다는 뜻이고, E123은 1,2,3중 어떤 것을 무조건 산다는 뜻이다. 우리는 E12,E13,E23을 계산할 때 E123을 한 번 더 빼서 다시 넣어야 한다. 이런 식으로 미루어 보면...
148D 코드
#include <stdio.h>
#include <string.h>
#define MAX 1100


double ans;
double win[MAX][MAX],lost[MAX][MAX];


int main()
{
	int i,j,n,m;
	
	
	while (scanf("%d%d",&n,&m) != EOF) {
		
		ans = 0;
		memset(win,0,sizeof(win));
		memset(lost,0,sizeof(lost));
		
		
		for (i = 1; i <= n; ++i)
			win[i][0] = 1.0;
		for (i = 1; i <= n; ++i)
			for (j = 1; j <= m; ++j) {
				
				win[i][j] = i * 1.0 / (i + j) + lost[i][j-1] * j * 1.0 / (i + j);
				lost[i][j]  = j * 1.0 / (i + j) * win[i-1][j-1] * (i * 1.0 / (i + j - 1));
				lost[i][j] += j * 1.0 / (i + j) * win[i][j-2] * ((j - 1) * 1.0 / (i + j - 1));
			}

			
			printf("%.9lf
",win[n][m]);
	}
}

SGU 495 코드:
#include <stdio.h>
#include <string.h>
#define MAX 1100000


int n,m;
double ans,dp[MAX],np[MAX];


int main()
{
	int i,j,k;


	while (scanf("%d%d",&n,&m) != EOF) {

		ans = 1;
		dp[1] = 1,dp[0] = 0;
		for (i = 2; i <= m; ++i) {
			
			dp[i] = dp[i-1] * np[i-1] + dp[i-1] * (dp[i-1] - 1.0/n);
			np[i] = 1-dp[i];
			ans += dp[i];
		}
		printf("%.10lf
",ans);
	}
}

Zoj 3383 코드
///*O(min(n,m)*min(n,m)*l)
import java.math.BigInteger;
import java.util.Scanner;

public class Zoj3380 {

	static BigInteger[][] C = new BigInteger[110][110];
	static BigInteger[][] dp = new BigInteger[110][110];
	
	
	static void Initial() {
		
		for (int i = 0; i < 110; ++i)
			C[i][0] = C[i][i] = BigInteger.ONE;
		for (int i = 2; i < 110; ++i)
			for (int j = 1;  j < i; ++j)
				C[i][j] = C[i-1][j].add(C[i-1][j-1]);
	}
	
	public static void main(String[] args) {
		
		Initial();
		Scanner cin = new Scanner(System.in);
		
		
		while (cin.hasNext()) {
			
			int m = cin.nextInt();
			int n = cin.nextInt();
			int l = cin.nextInt();
			if (l > m) {
				
				System.out.println("mukyu~");
				continue;
			}
			
			
			BigInteger total = BigInteger.valueOf(n).pow(m);
			if (l > m / 2) {
				
				BigInteger ans = BigInteger.ZERO;
				for (int i = l; i <= m; ++i)
					ans = ans.add(C[m][i].multiply(BigInteger.valueOf(n-1).pow(m-i)));
				ans = ans.multiply(BigInteger.valueOf(n));
				BigInteger gcd = ans.gcd(total);
				System.out.println(ans.divide(gcd)+"/"+total.divide(gcd));
			}
			else {
				
				for (int i = 0;i <= m; ++i)
					for (int j = 0; j <= m; ++j)
						dp[i][j] = BigInteger.ZERO;
				dp[0][0] = BigInteger.ONE;
				
				
				for (int i = 1; i <= n && i <= m; ++i)
					for (int j = 1; j <= m; ++j)
						for (int k = 1; k < l && k <= j; ++k)
							dp[i][j] = dp[i][j].add(dp[i-1][j-k].multiply(C[m-(j-k)][k]).multiply(BigInteger.valueOf(n-(i-1))));
				
				
				BigInteger ans = BigInteger.ZERO;
				BigInteger Jc = BigInteger.ONE;
				for (int i = 1; i <= m; ++i) {
				
					ans = ans.add(dp[i][m].divide(Jc));
					Jc = Jc.multiply(BigInteger.valueOf(i+1));
				}

				
				ans = total.subtract(ans);
				BigInteger gcd = ans.gcd(total);
				System.out.println(ans.divide(gcd)+"/"+total.divide(gcd));
			}
		}
	}
}//*/
/*O(m*m*l)
import java.math.BigInteger;
import java.util.Scanner;

public class Zoj3380 {

	static BigInteger[][] C = new BigInteger[110][110];
	static BigInteger[][] dp = new BigInteger[110][110];
	
	
	static void Initial() {
		
		for (int i = 0; i < 110; ++i)
			C[i][0] = C[i][i] = BigInteger.ONE;
		for (int i = 2; i < 110; ++i)
			for (int j = 1;  j < i; ++j)
				C[i][j] = C[i-1][j].add(C[i-1][j-1]);
	}
	
	public static void main(String[] args) {
		
		Initial();
		Scanner cin = new Scanner(System.in);
		
		
		while (cin.hasNext()) {
			
			int m = cin.nextInt();
			int n = cin.nextInt();
			int l = cin.nextInt();
			if (l > m) {
				
				System.out.println("mukyu~");
				continue;
			}
			
			
			BigInteger total = BigInteger.valueOf(n).pow(m);
			if (l > m / 2) {
				
				BigInteger ans = BigInteger.ZERO;
				for (int i = l; i <= m; ++i)
					ans = ans.add(C[m][i].multiply(BigInteger.valueOf(n-1).pow(m-i)));
				ans = ans.multiply(BigInteger.valueOf(n));
				BigInteger gcd = ans.gcd(total);
				System.out.println(ans.divide(gcd)+"/"+total.divide(gcd));
			}
			else {
				
				for (int i = 0;i <= n; ++i)
					for (int j = 0; j <= m; ++j)
						dp[i][j] = BigInteger.ZERO;
				dp[0][0] = BigInteger.ONE;
				
				
				for (int i = 1; i <= n; ++i)
					for (int j = 0; j <= m; ++j)
						for (int k = 0; k < l && k <= j; ++k)
							dp[i][j] = dp[i][j].add(dp[i-1][j-k].multiply(C[m-(j-k)][k]));
				BigInteger ans = total.subtract(dp[n][m]);
				BigInteger gcd = ans.gcd(total);
				System.out.println(ans.divide(gcd)+"/"+total.divide(gcd));
			}
		}
	}
}
10 20 3
176771177/800000000
*/

Zoj 3460 코드
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define MAX 20000


double dp[MAX], ans;
int c[MAX], vis[MAX];
int n, m, cost[MAX];


void Solve_DP() {

    memset(dp, 0, sizeof (dp));
    for (int i = 2 * c[n]; i >= m; --i) {

        for (int j = 1; j <= n; ++j)
            if(i > c[j]) dp[i] += cost[j];
            else dp[i] += 1 + dp[c[j] + i];
        dp[i] /= n;
    }
}
double Calculate(int att) {

    if (vis[att])
        return dp[att];
    vis[att] = 1;


    dp[att] = 0;
    for (int i = 1; i <= n; ++i)
        if (att > c[i])
             dp[att] += cost[i];
        else dp[att] += Calculate(att+c[i]) + 1;


    dp[att] /= n;
    return dp[att];
}


int main() {
    int i, j, k;


    while (scanf("%d%d", &n, &m) != EOF) {

        for (i = 1; i <= n; ++i)
            scanf("%d", &c[i]);
        sort(c + 1, c + 1 + n);
        for (i = 1; i <= n; ++i)
            cost[i] = (1 + sqrt(5)) / 2 * c[i] * c[i];


        //Solve_DP();
        //printf("%.3lf
", dp[m]);
        memset(vis,0,sizeof(vis));
        ans = Calculate(m);
        printf("%.3lf
",ans);
    }
}

Hdu 4405 코드
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 100010


int n,m,next[MAX];
double dp[MAX];


double Solve_DP(int day) {

	if (day >= n) return 0;
	if (dp[day]) return dp[day];


	if (next[day]) 
		dp[day] = Solve_DP(next[day]);
	else  {

		for (int i = 1; i <= 6; ++i)
			dp[day] += (Solve_DP(day + i) + 1) * 1/6.0;
	}
	return dp[day];
}
double Solve_DP1() {
	
	for (int i = n - 1; i >= 0; --i)
		if (next[i]) dp[i] = dp[next[i]];
		else  {
			
			for (int j = 1; j <= 6; ++j) {
				
				int k = i + j >= n ? n : i + j;
				dp[i] += (dp[k] + 1) * 1.0 / 6.0;
			}
		}
		
		
	return dp[0];
}


int main()
{
	int i,j,k,a,b;


	while (scanf("%d%d",&n,&m),n + m) {

		for (i = 0; i <= n; ++i)
			dp[i] = next[i] = 0;
		for (i = 1; i <= m; ++i) 
			scanf("%d%d",&a,&b),next[a] = b;

		
		printf("%.4lf
",Solve_DP1());
		//printf("%.4lf
",Solve_DP(0));
	}
}

 
http://wenku.baidu.com/view/90adb02acfc789eb172dc8a8.html
http://wenku.baidu.com/view/56147518a8114431b90dd81e.html
React.js - 컴포넌트
낙곡P2051 중국 장기【dp】

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage