「Bzoj 3191」「JLOI2013」卡牌游戏 (概率DP)

bzoj 3191
题意：见上。

根据题目，我们可以从终态入手。考虑什么状态下概率已定。(期望概率题入手套路)
这里可以发现只有一个人时，必定他会胜利，所以我们可以按照「人数」划分阶段。
那么可以设$dp(i,j)$为有$i$个人时，庄家开始数第$j$个人胜利的概率。(也可以设更加明显的三维状态)
那么$dp(i-1)$可以转移到$dp(i)$
从$i-1$到$i$, $i$下$j$的这个人是不动的。考虑$i$时淘汰一个人，即枚举$a[k]$使得$c=a[k] \mod i$，$c-1$是淘汰的人相对当前$i$庄家的位置。
然后因为淘汰了一个人庄家就是这个人的下一个，那么考虑两种情况
第一种，庄家跑不到$j$的后面，那么这时$dp(i,j)=\frac{dp(i-1,j-c)}m$，画图可知
第二种，庄家会跑到$j$的后面，那么这时$dp(i,j)=\frac{dp(i-1,j+(i-c))}m$，画图可知

那么最后$dp(n)$即为答案。

知识点：
1、从终态入手，来判断怎么划分DP状态

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    int n, m, a[55];
    db dp[55][55];

    void clean() {
        ms(dp, 0);
    }
    int solve() {

        clean();
        cin >> n >> m;
        for (int i = 1; i <= m; ++i) cin >> a[i];

        dp[1][1] = 1.0;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = 1; k <= m; ++k) {
                    int c = a[k] % i;
                    if (!c) c = i;
                    if (c < j)
                        dp[i][j] += dp[i - 1][j - c] / m;
                    else if (c > j)
                        dp[i][j] += dp[i - 1][j + (i - c)] / m;
                }
            }
        }

        for (int i = 1; i <= n; ++i) {
            printf("%.2f%% ", dp[n][i] * 100.0);
        }

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}