uva 542 France '98

제목: 제목은 하나의case로 16개 팀이 있고 이름을 제시한다. 그리고 다음은 16*16의 행렬이다. p[i][j]는 두 개의 정수로 i팀이 j팀을 이길 확률을 나타낸다. p[i][j]+p[j][i]=100, 아래 16행은 팀의 이름을 출력하고 그 다음 백분율은 이 팀이 전체 우승할 확률이다.
DP 스트리밍이나 기억력 검색 모두 가능합니다.
dp[i][left][right]를 설정하면 i팀은 제left에서 제right팀까지 우승할 확률을 나타낸다. 그래서 마지막으로 필요한 것은 dp[i][16]이다.한 팀이 면전에서 우승하려면 그 전에 우승해야 돼요.
그래서mid=(left+right)/2; 
i와 j가 [left,right]에서 우승을 쟁탈한다(예를 들어 i와 j가 1에서 16까지 우승을 쟁탈한다. 즉, 총 우승을 쟁탈한다). 그러면 i와 j는 반드시 두 구역에서 온 것이다.
left<=i<=mid, 그러면 dp[i][left][mid], dp[j][mid+1][right]를 획득해야 합니다.
mid+1<=i<=right, 그러면 dp[i][mid+1][right], dp[j][left][mid]
코드를 구체적으로 보시죠.
 
 
DP 스핀들

#include <cstdio>

#include <cstring>

double p[20][20],dp[20][20][20];

char name[20][50];



int main()

{

    int N=16;

    for(int i=1; i<=N; i++) scanf("%s",name[i]);

    for(int i=1; i<=N; i++)

        for(int j=1; j<=N; j++)

        { scanf("%lf",&p[i][j]); p[i][j]/=100; }



    int len,left,right,mid,i,j;



    memset(dp,0,sizeof(dp));

    for(int i=1; i<=N; i++) dp[i][i][i]=1;



    for(len=2; len<=N; len*=2)

        for(left=1; left<=N; left+=len)

        {

            right=left+len-1; mid=(left+right)/2;

            for(i=left; i<=mid; i++)

                for(j=mid+1; j<=right; j++)

                {

                    dp[i][left][right]+=p[i][j]*dp[i][left][mid]*dp[j][mid+1][right];

                    dp[j][left][right]+=p[j][i]*dp[i][left][mid]*dp[j][mid+1][right];

                }

        }

    for(i=1; i<=N; i++) printf("%-10s p=%.2f%%
",name[i],dp[i][1][N]*100);

    return 0;

}

 
DO 메모리 검색

#include <cstdio>

#include <cstring>



struct team

{

    char name[110];

    int n;

}a[20];

double p[20][20];

double dp[20][20][20];





void dfs(int i ,int left ,int right)

{

    if(dp[i][left][right]!=-1) return ;



    int mid=(left+right)/2;

    int l1,r1,l2,r2;



    if(i<=mid) {l1=left; r1=mid; l2=mid+1; r2=right;}

    else       {l1=mid+1; r1=right; l2=left; r2=mid;}



    dp[i][left][right]=0;

    for(int j=l2; j<=r2; j++)

    {

        dfs(i,l1,r1);  dfs(j,l2,r2);

        dp[i][left][right]+=p[i][j]*dp[i][l1][r1]*dp[j][l2][r2];

    }

}



int main()

{

    int N=16;

    for(int i=1; i<=N; i++)

    { scanf("%s",a[i].name); a[i].n=i; }



    for(int i=1; i<=N; i++)  

        for(int j=1; j<=N; j++)  

        { scanf("%lf",&p[i][j]); p[i][j]/=100; }



    for(int i=1; i<=N; i++) 

        for(int j=1; j<=N; j++) 

            for(int k=1; k<=N; k++) 

                dp[i][j][k]=-1;

    for(int i=1; i<=N; i++) dp[i][i][i]=1;



    int left=1,right=N,mid,l1,r1,l2,r2;



    mid=(left+right)/2;

    for(int i=left; i<=right; i++)

    {

        if(i<=mid) {l1=left; r1=mid; l2=mid+1; r2=right;}

        else       {l1=mid+1; r1=right; l2=left; r2=mid;}



        dp[i][left][right]=0.0;

        for(int j=l2; j<=r2; j++)

        {

            dfs(i,l1,r1);   dfs(j,l2,r2);

            dp[i][left][right]+=p[i][j]*dp[i][l1][r1]*dp[j][l2][r2];

        }

        printf("%-10s p=%.2f%%
", a[i].name , dp[i][left][right]*100);

    }



    return 0;

}