Editorial for Atcoder Educational DP Contest J - Sushi


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ncduy0303

Để giải bài này, bạn đọc nên nắm vững khái kiệm giá trị kỳ vọng qua bài viết trên VNOI Wiki

Gọi ~dp[x][y][z]~ là giá trị kỳ vọng cần tìm khi có ~x~ đĩa có ~1~ miếng sushi, ~y~ đĩa có ~2~ miếng sushi, và ~z~ đĩa có ~3~ miếng sushi.

Khi chuyển trạng thái quy hoạch động chú ý rằng mỗi khi ta giảm ~y~ hoặc ~z~ đi ~1~ thì ta phải tăng thêm ~1~ cho ~x~ hoặc ~y~ tương ứng. Ví dụ nếu Taro ăn một miếng sushi từ đĩa đang có ~2~ miếng sushi thì số lượng đĩa có ~2~ miếng sushi ~y~ sẽ giảm đi ~1~ và đồng thời số lượng đĩa có ~1~ miếng sushi ~x~ sẽ tăng thêm 1.

Quan sát hết tất cả các trường hợp có thể xảy ra tại trạng thái ~(x,y,z)~, ta có thể lập được công thức: ~dp[x][y][z] = 1 + \frac{n-(x+y+z)}{n} \cdot dp[x][y][z] + \frac{x}{n} \cdot dp[x-1][y][z] + \frac{y}{n} \cdot dp[x+1][y-1][z] + \frac{z}{n} \cdot dp[x][y+1][z-1]~

Sắp xếp lại biểu thức trên, ta có công thức quy hoạch động: ~dp[x][y][z] = \frac{n + x \cdot dp[x−1][y][z] + y \cdot dp[x+1][y−1][z] + z \cdot dp[x][y+1][z−1]}{x+y+z}~

Độ phức tạp: ~O(N^{3})~

Code tham khảo

#include <bits/stdc++.h>

using namespace std;

int n;
long double dp[301][301][301];

double memo(int x, int y, int z) {
    if (x < 0 || y < 0 || z < 0) return 0;
    if (x == 0 && y == 0 && z == 0) return 0;
    if (dp[x][y][z] > 0) return dp[x][y][z];

    long double ret = n + x * memo(x - 1, y, z) + y * memo(x + 1, y - 1, z) + z * memo(x, y + 1, z - 1); 
    return dp[x][y][z] = ret / (x + y + z);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    vector<int> a(n); vector<int> freq(3);
    for (int &x : a) cin >> x, freq[x - 1]++;

    memset(dp, -1, sizeof dp);

    cout << fixed << setprecision(10) << memo(freq[0], freq[1], freq[2]) << endl;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.