fzuoj 2145 Rock-Paper-Scissors Game

제목 여기.
사고방식: f[state]로fatbrother의 영향이 없는 상황에서maze가 이길 확률을 나타낸다.f[state] = 무승부 확률 * f[state] + sigma(pi* f[하위 상태]), f[state] = sigma(pi* f[하위 상태])/(1- 무승부 확률)
dp[state]로fatbrother가 있는 상황에서maze가 이길 확률을 나타낸다.한 걸음 한 걸음fatbrother의 결정을 일일이 열거한 다음에 최대치를 취하면 된다.
두 개의 보조 그룹을 사용하면mask[state][i]는state라는 집합에 있는 사람들이 모두 i를 낼 확률을 나타낸다.msk[state1][state2]는state1 개인의 집합 중,출권의 종류는state2의 확률(maze 포함),msk수조의 작용은 무승부의 확률을 계산하는 데 사용된다.이 문제는 카드가 꽉 끼어서 msk 최적화를 사용하기 전에 시간을 많이 초과했다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

double f[1 << 15],dp[1 << 15];
double a[25][5];
double mask[1 << 15][5];
double msk[1 << 15][8];
int rev[1 << 15];
int lowbit(int x)
{
    return x & (-x);
}

void solve()
{
    for(int i = 0; i < 15; i ++)
        rev[1 << i] = i;
    int n;
    scanf("%d",&n);
    for(int i = 0; i < 3; i ++) scanf("%lf",&a[n][i]);
    a[n][3] = a[n][0];
    a[n][4] = a[n][1];
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < 3; j ++)
            scanf("%lf",&a[i][j]);
        a[i][3] = a[i][0];
        a[i][4] = a[i][1];
    }
    mask[0][0] = mask[0][1] = mask[0][2] = mask[0][3] = mask[0][4] = 1;
    for(int i = 1; i < (1 << n); i ++) {
        int x = rev[lowbit(i)];
        for(int k = 0; k < 3; k ++)
            mask[i][k] = mask[i ^ lowbit(i)][k] * a[x][k];
        mask[i][3] = mask[i][0];
        mask[i][4] = mask[i][1];
    }
    for(int i = 0; i < (1 << n); i ++)
        for(int j = 0; j < 8; j ++)
            msk[i][j] = 0;
    for(int i = 0; i < 3; i ++)
        msk[0][1 << i] = a[n][i];
    for(int i = 1; i < (1 << n); i ++) {
        int x = rev[lowbit(i)];
        for(int k = 0; k < 8; k ++) {
            for(int j = 0; j < 3; j ++) {
                msk[i][k | (1 << j)] += msk[i ^ (1 << x)][k] * a[x][j];
            }
        }
    }
    f[0] = 1;
    for(int i = 1; i < (1 << n); i ++) {
        double tmp, p = 0;
        double tot = 0;
        for(int j = i; j; j = (j - 1) & i) {
            tmp = mask[j][0] * a[n][1] * mask[i ^ j][1] + mask[j][1] * a[n][2] * mask[i ^ j][2] + mask[j][2] * a[n][3] * mask[i ^ j][3];
            tot += tmp * f[i ^ j];
            //p += tmp;
            //p += mask[j][1] * a[n][0] * mask[i ^ j][0] + mask[j][2] * a[n][1] * mask[i ^ j][1] + mask[j][3] * a[n][2] * mask[i ^ j][2];
        }
        p = msk[i][7] + msk[i][1] + msk[i][2] + msk[i][4];
        f[i] = tot / (1 - p);
    }
    dp[0] = max(a[n][1] / (1 - a[n][0]),a[n][2] / (1 - a[n][1]));
    dp[0] = max(dp[0],a[n][3] / (1 - a[n][2]));
    for(int i = 1; i < (1 << n); i ++) {
        double maxn = 0;
        for(int j = 1; j <= 3; j ++) {
            double p = 0,tot = 0;
            for(int k = i; ; k = (k - 1) & i) {
                if(k) {
                    tot += mask[k][j - 1] * a[n][j] * mask[k ^ i][j] * dp[k ^ i];
                    //p += mask[k][j - 1] * a[n][j] * mask[k ^ i][j];
                    //p += mask[k][j + 1] * a[n][j] * mask[k ^ i][j];
                }
                tot += mask[k][j] * a[n][j + 1] * mask[k ^ i][j + 1] * f[k ^ i];
                //p += mask[k][j] * a[n][j + 1] * mask[k ^ i][j + 1];
                //p += mask[k][j] * a[n][j - 1] * mask[k ^ i][j - 1];
                if(!k) break;                
            }
            for(int k = 0; k < 8; k ++) {
                int x = k | (1 << (j == 3 ? 0 : j));
                if(x == 7 || x == 1 || x == 2 || x == 4) p += msk[i][k];
            }
            maxn = max(maxn,tot / (1 - p));    
        }
        dp[i] = maxn;
    }
    printf("%.10lf
",dp[(1 << n) - 1]);
}
        
int main()
{
    int t;
    scanf("%d",&t);
    while(t --) {
        solve();
    }
    return 0;
}