1 条题解
-
0
[J] Sushi(dp_j)题解
题意简述
个盘子,第 个有 个寿司。每次等概率选一个盘子,有寿司就吃一个。求吃完所有寿司的期望操作次数。
思路
状态压缩:只关心"有几盘剩几片"
关键观察:盘子的编号不重要,只关心还剩 片、 片、 片的盘子各有多少个。设状态 表示剩 片的盘子数分别为 。
期望方程的推导
每次操作:
- 以概率 选到"剩 1 片"的盘子 → 状态变 ;
- 以概率 → (剩 2 片的盘子变成剩 1 片);
- 以概率 → ;
- 以概率 选到空盘 → 状态不变(但仍算一次操作)。
设 为从该状态到结束的期望步数,则
$$f(i,j,k) = 1 + \frac{i}{N} f(i-1,j,k) + \frac{j}{N} f(i+1,j-1,k) + \frac{k}{N} f(i,j+1,k-1) + \frac{N-i-j-k}{N} f(i,j,k).$$把右边的 移项,两边乘 ,利用 :
$$f(i,j,k) = \frac{N + i\,f(i-1,j,k) + j\,f(i+1,j-1,k) + k\,f(i,j+1,k-1)}{i+j+k}.$$这是一条显式递推(不再自引用),可以直接 DP。
递推顺序与内存
依赖关系:
- :同层 、更小 ✅( 升序已算);
- :同层 、更小 ✅( 升序已算, 虽然更大但那是 那一轮);
- :上一层 ✅( 升序已算)。
所以循环按 升序、 升序、 升序,并只保留 与 两层。内存 个
double, 时约 1.5 MB。答案 。
复杂度
状态数 ,每次 转移,总 ;时间可接受,空间 。
参考代码
#include <cstdio> #include <cstring> using namespace std; static double cur[305][305], prv[305][305]; int main() { int n; scanf("%d", &n); int c[4] = {0, 0, 0, 0}; for (int i = 0; i < n; i++) { int a; scanf("%d", &a); c[a]++; } for (int k = 0; k <= c[3]; k++) { for (int j = 0; j + k <= n; j++) { for (int i = 0; i + j + k <= n; i++) { if (i + j + k == 0) { cur[i][j] = 0.0; continue; } double v = n; if (i > 0) v += i * cur[i - 1][j]; if (j > 0) v += j * cur[i + 1][j - 1]; if (k > 0) v += k * prv[i][j + 1]; cur[i][j] = v / (i + j + k); } } memcpy(prv, cur, sizeof(cur)); } printf("%.12f\n", cur[c[1]][c[2]]); return 0; }易错点
- 不要开 的数组:那是约 218 MB,会 MLE。按 分层只留两层(1.5 MB)。
- 转移顺序必须满足"依赖先算": 升序 → 升序 → 升序( 用同层更小的、 用同层上一轮、 用上一层)。
- 分母是 ,不是 ——空盘不贡献进度,但贡献了那一次操作(已体现在分子里的 )。
- 答案以 为下标取出:答案状态是"剩 1 片 个、剩 2 片 个、剩 3 片 个( 已推进到 )"。
数据说明
共 19 组:4 组官方样例(含期望 的 ); 的 、、全 的 ; 随机; 全 、全 、全 与两类偏分布(最坏 与最大值 )。
- 1
信息
- ID
- 19
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者