3029: 수위자의 도전 확률과 기대DP

4880 단어
3차원 DP, 방정식은 쓰기 쉽다. fi, j, k는 전 i개에 도전하고 j회를 이겼으며 현재 수익은 k의 확률을 나타낸다.그러면fi,j,k=fi-3,j-1,k-3,si∗pi+fi-1,j,k∗(1-pi) 우리는 k>n일 때 이 상태가 아무런 의미가 없다는 것을 알 수 있다. 왜냐하면 이때 이후에 어떻게 설치해도 k<0이 되지 않기 때문에 k>n의 상태를 k=n의 상태로 하면 된다.처음에는 멍청해서 옮길 때 일부 상태를 적게 옮겼다.쓰기 편하도록 현재 상태에서 뒤로 옮기는 것이 좋다.
#include<iostream>
#include<cstdio>
using namespace std;
int n,l,K;
double ans;
double p[201];
double f[201][201][401];
int s[201];
inline int read()
{
    int a=0,f=1; char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
    while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}
    return a*f;
}
int main()
{
    n=read(); l=read(); K=read();
    for (int i=1;i<=n;i++)
    {
        int x=read();
        p[i]=x/100.0;
    }
    for (int i=1;i<=n;i++) s[i]=read();
    f[0][0][K+n]=1;
    for (int i=1;i<=n;i++)
        for (int j=0;j<=n;j++)
            for (int k=0;k<=n+n+s[i];k++)
            {
                int x=k+s[i];
            //  int x=k-s[i];   f[i-1][j-1][k-s[i]+1..k]       !
                if (x<=0) x=0; 
                if (x>=n+n) x=n+n; 
                f[i][j+1][x]+=f[i-1][j][k]*p[i];
            //  if (j!=0) f[i][j][k]+=f[i-1][j-1][x]*p[i];
                f[i][j][k]+=f[i-1][j][k]*(1-p[i]);
            }
    for (int j=l;j<=n;j++)
        for (int k=n;k<=n+n;k++)
            ans+=f[n][j][k];
    printf("%.6lf
"
,ans); return 0; }

좋은 웹페이지 즐겨찾기