Round F 2020 - Kick Start 2020 Yeetzhee（期望，記憶化搜索）

Problem
Pommel is very bored at home so she has invented a new game involving N dice. Each die has the numbers from 1 to M written on it. Whenever she throws a die, it has an equal probability of landing on each of the M possible values.

Pommel places all the dice in a row. She goes through the dice one at a time from left to right. For each die she rolls, Pommel can either keep the value she rolled and move on to the next die or she can re-roll the die. Pommel can re-roll a die as much as she wants before moving on to the next die.

Once Pommel has gone through all the dice, the game is finished. To determine if she has won, she puts the dice into groups. All dice with the same value are put into the same group. So if she finishes the game with x distinct values, then there will be x groups. These groups of dice are then sorted by number of dice in non-decreasing order.

For example:
If the final dice results are [2, 2, 3, 2, 2, 3], the dice would be put into two groups and ordered as follows: [3, 3] and [2, 2, 2, 2].
If the final dice results are [1, 6, 7, 7], the dice would be put into three groups and ordered as follows: [6], [1], and [7, 7] (or equivalently, [1], [6] and [7, 7]).

Pommel wins if she finishes the game with exactly K groups, and the i-th group contains exactly Ai dice, for all i.

What is the expected value of the total number of dice rolls it will take Pommel to win the game, assuming she plays optimally to minimize this expected value?

It is guaranteed that for any valid input, it is possible for Pommel to win the game.

Input
The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case contains the integers N, M and K. Then, K lines follow describing the groups she must finish with. The i-th line contains Ai.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the expected number of times it will take to roll all the dice for Pommel to win the game.

y will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ K ≤ M.
1 ≤ Ai, for all i.
A1 + A2 + … + AK = N.
Ai ≤ Ai+1, for all i.

Test Set 1
2 ≤ N ≤ 6.
2 ≤ M ≤ 6.

Test Set 2
2 ≤ N ≤ 50.
2 ≤ M ≤ 50.

Sample

Input

Output

2
3 6 2
1
2
5 2 1
5

Case #1: 4.7
Case #2: 9.0

In Sample case #1, Pommel has N = 3 dice, each with a number from 1 to M = 6 written on them. To win, she must finish the game with K = 2 groups. One group must have one die (A1 = 1), while the other group must have two dice (A2 = 2). One optimal strategy for Pommel is as follows:
Pommel throws the first die once.
Pommel throws the second die once.
If the first and second dice are the same, Pommel keeps throwing the third die until it ends in a different value from the first two. It takes 1.2 dice rolls on average.
If the first and second dice are different, Pommel keeps throwing the third die until it matches the first or the second die. It takes 3 dice rolls on average.
This strategy takes Pommel 4.7 (1 + 1 + 1/6 × 1.2 + 5/6 × 3) dice rolls on average.

In Sample case #2, Pommel has N = 5 dice, each with a number from 1 to M = 2 written on them. To win, she must finish the game with K = 1 group, with all N dice in them (A1 = N). For the first die, Pommel rolls it once. Then, for each remaining die she keeps rolling until it has the same value as the first one. It takes 2 dice rolls on average.

This strategy takes Pommel 9 (1 + 2 + 2 + 2 + 2) dice rolls on average.

參考lee 215題解（可以去油管搜索，就不放鏈接了）

題意：
n個骰子，每個骰子有m面顏色，
你可以無限擲骰子，知道弄到了你想要的面，
結果就是相同顏色的篩子合并，最后陣列為A，求最優策略下的期望步數

思路：
維護當前陣列B（代表每一種顏色的數目）
結果陣列A（每種顏色的期望數目）

貪心的考慮，對于某個顏色，只要其還沒有達到上限（不超過A陣列），那就可以拿來用，

于是最暴力的想法，就是將當前陣列B當做狀態，并且將A,B陣列排序，
列舉當前選擇的顏色是什么，然后更新B陣列，如果B陣列排序以后不超過A陣列（對應位不大于），那就可以，

期望的運算元就是所有合法操作的dfs(子狀態)的值和sum，
假設合法操作次數為pos，那么子狀態的期望操作次數為 s u m p o s \frac{sum}{pos} possum?，
我們會重復投擲當前骰子直到得到一個合法顏色，期望次數為 m p o s \frac{m}{pos} posm?，

然后對于B陣列記錄狀態，

但是這里可以有剪枝（其實等同于上面的排序）

同時因為顏色沒有區別，在乎的只是數量，所以可以把顏色數量相同的合并，當這個范圍的任意一個顏色出現，結果都是一樣，

比如當前陣列 3 3 3 3 5，前面4個3可以合并，然后選到前四種顏色的結果，對于數量來說都是3 3 3 4 5，初始狀態是0 0 0 0 0 0，那么選到任意一種顏色結果都是0 0 0 0 0 1，

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int maxn = 55;
map<vector<int>,double>mp;
map<vector<int>,int>vis;
vector<int>target;

double dfs(vector<int>vec) {
    if(vis[vec]) return mp[vec];
    double pos = 0;
    double res = 0;
    for(int i = 0;i < vec.size();i++) {
        int j = i;
        while(j + 1 < vec.size() && vec[j + 1] == vec[i]) {
            j++;
        }
        if(vec[j] + 1 <= target[j]) {
            vec[j]++;
            pos += j - i + 1;
            res += dfs(vec) * (j - i + 1);
            vec[j]--;
        }
        i = j;
    }
    res = res / pos + (double)vec.size() / pos;
    mp[vec] = res;
    vis[vec] = 1;
    return res;
}

int main() {
    int T;scanf("%d",&T);
    int kase = 0;
    while(T--) {
        int n,m,k;scanf("%d%d%d",&n,&m,&k);
        mp.clear();
        vis.clear();
        target.clear();
        for(int i = 1;i <= m - k;i++) {
            target.push_back(0);
        }
        for(int i = 1;i <= k;i++) {
            int x;scanf("%d",&x);
            target.push_back(x);
        }
        mp[target] = 0.0;
        vis[target] = 1;
        vector<int>vec;
        for(int i = 0;i < m;i++) vec.push_back(0);
        printf("Case #%d: %.5f\n",++kase,dfs(vec));
        
    }
    return 0;
}