当前位置: 首页 > news >正文

概率期望dp 复习笔记

Sushi

给你 \(n(1\leq n\leq 300)\) 碗寿司,每碗寿司有 \(a_i(1\leq a_i\leq 3)\) 个,每次进行如下操作:

  • 等概率地得到一个 \(i\),然后如果当前的 \(a_i>0\),就让 \(a_i-1\),否则就不需要做任何事。

求全部吃完的期望操作次数。

题目分析

注意到 \(a_i\in[1,3]\),故设 \(f_{i,j,k}\) 表示现在碗里只有 \(1\) 个的有 \(i\) 碗,只有 \(2\) 个的有 \(j\) 碗,只有 \(3\) 个的有 \(k\) 碗。

我们发现从 \(f_{x,y,z}\) 推到 \(f_{0,0,0}\) 是复杂的。

不妨将整个过程反过来变成生产寿司从 \(f_{0,0,0}\) 推到 \(f_{x,y,z}\) 即可。

那么我们有转移:

\[f_{i,j,k}=\frac{n-i-j-k}{n}(f_{i,j,k}+1)+\frac{i}{n}(f_{i-1,j,k}+1)+\frac{j}{n}(f_{i+1,j-1,k}+1)+\frac{k}{n}(f_{i,j + 1,k-1}+1) \]

化简有:

\[(i+j+k)f_{i,j,k}=\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}+n \]

最后再除过去就可以了,于是你写出了以下的代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <iomanip>
#define int long long
#define N 305
using namespace std;
int n,a[N];
double f[N][N][N];
int sum1,sum2,sum3;
signed main(){cin >> n;for (int i = 1;i <= n;i ++) scanf("%lld",&a[i]);f[0][0][0] = 0.0;for (int i = 1;i <= n;i ++) sum1 += (a[i] == 1),sum2 += (a[i] == 2),sum3 += (a[i] == 3);for (int i = 0;i <= n;i ++)for (int j = 0;j <= n;j ++)for (int k = 0 + (i == j && j == 0);i + j + k <= n;k ++) {if (i) f[i][j][k] = f[i - 1][j][k] * i + f[i][j][k];if (j) f[i][j][k] = f[i + 1][j - 1][k] * j + f[i][j][k];if (k) f[i][j][k] = f[i][j + 1][k - 1] * k + f[i][j][k];f[i][j][k] = (f[i][j][k] + n) / (i + j + k);}cout << fixed << setprecision(10) << f[sum1][sum2][sum3];return 0;
}

这是错的,因为在转移 \(j\) 可行的时候,f_{i+1,j-1,k} 还没有被更新。

这似乎更那个区间 \(dp\) 直接枚举 \(i,j\) 一样是有问题的,于是我们可以像区间 \(dp\) 那样子先枚举长度就行了。

于是你得到:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <iomanip>
#define int long long
#define N 305
using namespace std;
int n,a[N];
double f[N][N][N];
int sum1,sum2,sum3;
signed main(){cin >> n;for (int i = 1;i <= n;i ++) scanf("%lld",&a[i]);f[0][0][0] = 0.0;for (int i = 1;i <= n;i ++) sum1 += (a[i] == 1),sum2 += (a[i] == 2),sum3 += (a[i] == 3);for (int len = 1;len <= n;len ++)for (int i = 0;i <= n;i ++)for (int j = 0;i + j <= len;j ++) {int k = len - i - j;f[i][j][k] = 0;if (i) f[i][j][k] += f[i - 1][j][k] * i;if (j) f[i][j][k] += f[i + 1][j - 1][k] * j;if (k) f[i][j][k] += f[i][j + 1][k - 1] * k;f[i][j][k] = (f[i][j][k] + n) / (i + j + k);}cout << fixed << setprecision(10) << f[sum1][sum2][sum3];return 0;
}

这还是错的,同样的错误,应该从 \(k\)\(j\) 枚举。

代码

时间复杂度 \(\mathcal{O}(n^3)\),代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <iomanip>
#define int long long
#define N 305
using namespace std;
int n,a[N];
double f[N][N][N];
int sum1,sum2,sum3;
signed main(){cin >> n;for (int i = 1;i <= n;i ++) scanf("%lld",&a[i]);f[0][0][0] = 0.0;for (int i = 1;i <= n;i ++) sum1 += (a[i] == 1),sum2 += (a[i] == 2),sum3 += (a[i] == 3);for (int len = 1;len <= n;len ++)for (int k = 0;k <= len;k ++)for (int j = 0;k + j <= len;j ++) {int i = len - k - j;f[i][j][k] = 0;if (i) f[i][j][k] += f[i - 1][j][k] * i;if (j) f[i][j][k] += f[i + 1][j - 1][k] * j;if (k) f[i][j][k] += f[i][j + 1][k - 1] * k;f[i][j][k] = (f[i][j][k] + n) / (i + j + k);}cout << fixed << setprecision(10) << f[sum1][sum2][sum3];return 0;
}
http://www.hskmm.com/?act=detail&tid=24968

相关文章:

  • 2025.10
  • PCIe扫盲——物理层逻辑部分基础(一)
  • 仅需3%训练数据的文本归一化技术
  • 价值原语博弈协议:价值原语共识锚定原则
  • 实用指南:工作流引擎-16-开源审批流项目之 整合Flowable官方的Rest包
  • 25fall做题记录-October - Amy
  • 嗯嗯
  • PCIe扫盲——AckNak 机制详解(二)
  • ASP.NET Core SignalR 身份认证集成指南(Identity + JWT) - 详解
  • utorrent 2.2.1
  • 2025热缩管厂家 TOP 企业品牌推荐排行榜,氟橡胶,双壁,线缆标识,防滑花纹,DR 耐油橡胶,PVDF,标识,航插用,军用热缩管公司推荐!
  • 市场交易反心理特征之八:劣仓驱逐良仓
  • 做题笔记18
  • 2025桩基检测机构最新企业咨询服务推荐排行榜,海上桩基检测,水上桩基检测服务推荐这十家公司!
  • 算法坑点
  • [省选联考 2025] 图排列 题解
  • Windows下安装并采用kubectl查看K8S日志
  • 实用指南:UV 包管理工具:替代 pip 的现代化解决方案
  • C/C++与Java、Python、Go在各个阶段的区别
  • 古典密码之凯撒密码
  • vi/vim文本编辑器
  • AI一周资讯 250926-251005
  • B3869 [GESP202309 四级] 进制转换-题解
  • 物理
  • springcloud gateway Error creating bean with name bootstrapImportSelectorConfiguration:
  • 完整教程:PyCharm接入DeepSeek,实现高效AI编程
  • Nginx的核心功能及实现
  • 2025焚烧炉厂家权威推荐,技术实力与市场口碑深度解析
  • 高考加油!UI界面生成器! - 教程
  • UnityShader入门精要-系统语义与函数体