Hướng dẫn giải của Atcoder Educational DP Contest J - Sushi


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: 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;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.