수학 적 기대 DP 소결

최근 에 수학 적 기대 DP 를 배 웠 는데 아직도 징 그 럽 습 니 다. 그러나 다른 DP 에 비해 생각 이 좋 습 니 다. 주요 한 사고방식 은 선형 DP 와 유사 합 니 다. 주로 확률 계산 은 덧셈 원리 의 더하기 방식 을 이용 하 는 것 입 니 다. 그리고 배열 아래 에 마이너스 로 표 시 된 상황 을 피하 고 이동 해 야 합 니 다.

Tyvj 1864 수비 자의 도전 은 비교적 간단 한 수학 확률 DP 이 므 로 음수 조 의 하 표 에 주의해 야 한다.f [i] [j] [k] 는 전 i 경기 에서 j 경기 의 용량 을 이 겼 다 고 밝 혔 다. - 지도 가 k 일 확률 이 있 고 상태 전 이 는: 이기 면 i + 1, j + 1, k 가 해당 하 는 변 화 를 해서 졌 다. i + 1, j 가 변 하지 않 고 k 가 변 하지 않 는 다

.

#include
#include
#include
using namespace std;
const int maxn=200+10;
int n,t,l;
double p[maxn];
int a[maxn];
double f[maxn][maxn][maxn+200]; // f[i][j][k]    i    j    -   k    
int main(){
    scanf("%d%d%d",&n,&l,&t);
    for(int i=1;i<=n;i++){
        scanf("%lf",&p[i]);
        p[i]/=100;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    if(t>n)t=n;
    f[0][0][t+200]=1;            //k 200       
    for(int i=0;ifor(int j=0;j<=n;j++){
            for(int k=-n;k<=n;k++){
                if(a[i+1]==-1){
                    f[i+1][j][k+200]+=f[i][j][k+200]*(1-p[i+1]);
                    f[i+1][j+1][k-1+200]+=f[i][j][k+200]*p[i+1];    
                }
                else {
                    f[i+1][j+1][min(k+a[i+1],n)+200]+=f[i][j][k+200]*p[i+1];
                    f[i+1][j][k+200]+=f[i][j][k+200]*(1-p[i+1]);
                }
            }
        }
    }
    double ans=0;
    for(int j=l;j<=n;j++){
        for(int k=0;k<=n;k++){
            ans+=f[n][j][k+200];    
        }
    }
    printf("%.6lf",ans);
    return 0;
}

Tyvj 2002 카드 f [a] [b] [c] [d] [x] [y] 는 현재 이미 a 장의 스페이드, b 장의 붉 은 복숭아, c 장의 매화, d 장의 사각형 을 뒤 집 었 고 왕 군 상 태 는 x 이 며 대왕 상 태 는 y 시의 기대 치 를 기록 했다.x = 4 는 왕 군 을 써 본 적 이 없다 는 뜻 이 고, x = 0 ~ 3 은 왕 군 을 써 본 적 이 있 고 그 에 상응하는 수가 된다 는 뜻 이다.초기 상태 f [0] [0] [0] [0] [4] [4]. 크 고 작은 왕 에 게 넘 기 려 면 판단 을 하고 최소 치 를 취하 고 크 고 작은 왕 이 넘 긴 후에 sum 의 값 을 추가 해 야 합 니 다.

#include
#include
#include
#include
using namespace std;
double f[20][20][20][20][5][5];
int vis[20][20][20][20][5][5];
int A,B,C,D;
double dp(int a,int b,int c,int d,int x,int y){

    if(vis[a][b][c][d][x][y]) return f[a][b][c][d][x][y];
    else vis[a][b][c][d][x][y]=1;

    int tot[4];
    tot[0]=a;tot[1]=b;tot[2]=c;tot[3]=d;
    tot[x]++;tot[y]++;

    if(tot[0]>=A&&tot[1]>=B&&tot[2]>=C&&tot[3]>=D) return f[a][b][c][d][x][y]=0.000;

    double ans=0;
    int sum=a+b+c+d;
    if(x!=4)sum++;
    if(y!=4)sum++;

    if(a<13) ans+=dp(a+1,b,c,d,x,y)*(13-a)/(54-sum);
    if(b<13) ans+=dp(a,b+1,c,d,x,y)*(13-b)/(54-sum);
    if(c<13) ans+=dp(a,b,c+1,d,x,y)*(13-c)/(54-sum);
    if(d<13) ans+=dp(a,b,c,d+1,x,y)*(13-d)/(54-sum);    

    if(x==4){
        double minnn=1000000;
        for(int i=0;i<=3;i++){
            minnn=min(minnn,dp(a,b,c,d,i,y)/(54-sum));  

        }ans+=minnn;
    }
    if(y==4){
        double minn2=1000000;
        for(int i=0;i<=3;i++){
            minn2=min(minn2,dp(a,b,c,d,x,i)/(54-sum));  

        }ans+=minn2;
    }

    f[a][b][c][d][x][y]=ans+1.000;
    return f[a][b][c][d][x][y];
}
int main(){
    scanf("%d%d%d%d",&A,&B,&C,&D);
    double goal=dp(0,0,0,0,4,4);
    if(goal>54) printf("-1.000");
    else
        //printf("%.3lf",goal);
        cout<3)<return 0;
}

왜 tyvj (쓰레기 OJ) printf 가 WA 를...
또 하나의 tyvj 1933 도 수학 적 기대 인 것 같은 데...

                                                  HelenKeller
                                                   2016.7.2