ZOJ 3735 Josephina and RPG DP

C (3, m) * C (3, m) 의 행렬 ko, ko [i] [j] 를 제시 하여 제 i 조 가 제 j 조 를 이 길 확률 을 표시 합 니 다. 시작 할 때 우리 측은 임의로 하 나 를 선택 할 수 있 습 니 다. 그리고 전투 에서 상대방 의 한 조 를 이 길 때마다 우리 측의 현재 조합 을 상대방 이 패배 한 그룹 으로 바 꿀 수 있 습 니 다.다음은 n 개의 상대방 의 조합 을 제시 하고 우리 측 이 어떻게 선택 하 느 냐 고 물 으 면 주어진 순서에 따라 상대방 의 모든 조합 을 이 길 확률 이 가장 크다.
      dp [j] [i] 로 상대방 의 i 번 째 조합 을 격파 할 때 우리 측의 조합 은 j 이 고 dp [j] [1] 에 대해 서 는 ko [j] [anti [1] (anti [j] 는 상대방 의 j 번 째 조합 을 나타 낸다) 로 직접 할당 할 수 있 습 니 다. 그 다음 dp [j] [i] 에 대해 서 는 j = anti [i - 1] 이 라면 순환 k = 0 - n - 1, dp [k] [i] = max (dp [k] [i], dp [k] [i] [k] * ko [k] [anti [i]]]]]),그룹 k 로 i - 1 을 물리 치고 i 를 계속 물리 친 다 는 뜻 이다.또한 dp [j] [i] = max (dp [k] [i - 1] * ko [j] [anti [i]]]) 의 최대 치 는 조합 k 로 i - 1 을 물리 치고 조합 을 교환 한 후 새로운 조합 j 로 i 를 물리 칩 니 다.만약 j! =anti [i - 1] 의 경우, dp [j] [i] = dp [j] [i - 1] * ko [j] [anti [i]] 를 직접 건 네 주면 됩 니 다. 선택 할 수 없 기 때문에 --... 마지막 으로 dp [i] [m] 에서 최대 치 를 찾 으 면 됩 니 다.
     

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
int n,m;
double dp[300][10100];
double ko[300][300];
int t[10100];
int main()
{
//    freopen("in.txt","r",stdin);
    while(~scanf("%d",&n))
    {
        n=n*(n-1)*(n-2);
        n=n/6;

        for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
        scanf("%lf",&ko[i][j]);

        scanf("%d",&m);
        for (int i=1; i<=m; i++)
        scanf("%d",&t[i]);

        for (int i=0; i<n; i++)
         for (int j=0; j<n; j++)
          dp[i][j]=0.0;
        for (int i=0; i<n; i++)
        dp[i][1]=ko[i][t[1]];

        for (int i=2; i<=m; i++)
         for (int j=0; j<n; j++)
         {
          if (j==t[i-1])
          {
            double res=0.0,res1=0.0;
            for (int k=0; k<n; k++)
            {
                res=max(res,dp[k][i-1]*ko[j][t[i]]);
                dp[k][i]=max(dp[k][i],dp[k][i-1]*ko[k][t[i]]);
            }
            dp[j][i]=res;

          }
          else dp[j][i]=dp[j][i-1]*ko[j][t[i]];
         }
         double ans=0.0;
         for (int i=0; i<n; i++) ans=max(ans,dp[i][m]);
         printf("%.6lf
",ans);

    }
    return 0;
}