Hướng dẫn giải của Atcoder Educational DP Contest J - Sushi
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ả:
Để 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