ZOJ 3711 Give Me Your Hand

佚名 6年前 (2019-04-13) 随笔 1543人围观抢沙发百度已收录

\[ \begin{eqnarray*} 题意：一个寝室有k个人(包过a, b)，a要玩游戏，b阻止a玩游戏(最多阻止m次)，问剩余阻止的期望 \end{eqnarray*} \]

\[ \begin{eqnarray*} & a &做坏事的条件：在寝室连续呆了T分钟，或者被阻止后T分钟\\ & a &不做坏事的条件：离开寝室或者被阻止 \end{eqnarray*} \]

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

\[ 已知门开关m次的时间，但不知道谁进出 \]

\[ \begin{eqnarray*} &&dp[i][j][k][l]\\ &&i表示第i次开门\\ &&j用二进制表示a,b在不在\\ &&k表示开始玩游戏的时间\\ &&l表示剩下几次阻止\\ &&进行dp转移，具体看代码 \end{eqnarray*} \]

#include<bits/stdc++.h>

using namespace std;

int T, N, M, K;
int arr[110];
double dp[110][4][110][110];//00 no a, b 01 a 10 b 11 a, b

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d %d %d", &T, &N, &M, &K);
        for(int i = 1; i <= N; ++i) scanf("%d", arr + i);
        memset(dp, 0, sizeof dp);
        dp[0][0][0][M] = 1.0;
        for(int i = 1; i <= N; ++i)
        {
            int sub = arr[i] - arr[i - 1];
            //0
            for(int j = 0; j <= M; ++j)
            {
                dp[i][0][0][j] += dp[i - 1][0][0][j] * (K - 2.0) / K;
                dp[i][1][0][j] += dp[i - 1][0][0][j] * 1.0 / K;
                dp[i][2][0][j] += dp[i - 1][0][0][j] * 1.0 / K;
            }
            //1
            for(int j = 0; j <= T; ++j)
            {
                for(int k = 0; k <= M; ++k)
                {
                    dp[i][0][0][k] += dp[i - 1][1][j][k] * 1.0 / K;
                    dp[i][1][min(T, j + sub)][k] += dp[i - 1][1][j][k] * (K - 2.0) / K;
                    if(j + sub >= T)
                    {
                        dp[i][3][0][max(0, k - 1)] += dp[i - 1][1][j][k] * 1.0 / K;
                    }
                    else
                    {
                        dp[i][3][j + sub][k] += dp[i - 1][1][j][k] * 1.0 / K;
                    }
                }
            }
            //2
            for(int j = 0; j <= M; ++j)
            {
                dp[i][0][0][j] += dp[i - 1][2][0][j] * 1.0 / K;
                dp[i][2][0][j] += dp[i - 1][2][0][j] * (K - 2.0) / K;
                dp[i][3][0][j] += dp[i - 1][2][0][j] * 1.0 / K;
            }
            //3
            for(int j = 0; j <= T; ++j)
            {
                for(int k = 0; k <= M; ++k)
                {
                    dp[i][1][(j + sub) % T][max(0, k - (j + sub) / T)] += dp[i - 1][3][j][k] * 1.0 / K;
                    dp[i][2][0][max(0, k - (j + sub) / T)] += dp[i - 1][3][j][k] * 1.0 / K;
                    dp[i][3][(j + sub) % T][max(0, k - (j + sub) / T)] += dp[i - 1][3][j][k] * (K - 2.0) / K;
                }
            }
        }
        int sub = 1440 - arr[N];
        double ans = 0;
        for(int i = 0; i < 4; ++i)
        {
            for(int j = 0; j <= T; ++j)
            {
                for(int k = 0; k <= M; ++k)
                {
                    if(i != 3) ans += dp[N][i][j][k] * k;
                    else ans += dp[N][i][j][k] * max(0, k - (j + sub) / T);
                }
            }
        }
        printf("%.6f\n", ans);
    }
    return 0;
}