### Decsription

  数据范围:\(n<=3000,m<=300\),保证\(\forall i,\sum\limits_{j}p_{ij}=1000\)

  

Solution

  日常期望算不对。。

  首先比较明显的一点是,每种类型是独立的,我们可以分开来考虑

  先来想一个比较直接的dp

  用\(a[i][j]\)表示第\(i\)个人最喜欢\(j\)的概率,记\(f[c][i][j]\)表示前\(i\)个人里面恰好有\(j\)个人最喜爱类型\(c\),转移显然:

\[f[c][i][j]=f[c][i-1][j]*(1-a[i][j])+f[c][i-1][j-1]*a[i][j]
\]

  再考虑用\(g[i][j]\)表示第\(i\)种钞票携带了\(j\)张,期望拿走的数量,那么有转移:

\[\begin{aligned}
g[i][j]&=\sum\limits_{k=0}^mmin(k,j)*f[i][n][k]\\
&=\sum\limits_{k=0}^j k*f[i][n][k]+\sum\limits_{k=j+1}^mj*f[i][n][k]\\
\end{aligned}
\]

  然后我们就可以用一个背包求出答案了,但是这样无论是空间还是时间都很爆炸

  

​  考虑\(\nabla g[i][j]=g[i][j]-g[i][j-1]\),也就是\(\nabla g[i][j]=\sum\limits_{k=j}^m f[i][n][k]\),首先注意到\(f[i][n][k]\)在\(i\)确定的情况下大小一定是随着\(k\)的增大而增大的,然后再看回这个\(\nabla g[i][j]\),显然这个东西的值应该是非负的,并且当\(i\)一定,\(\nabla g[i][j]\)的值随着\(j\)的增大而单调不升

​  所以我们可以得到一个结论,当\(i\)确定的时候,\(g[i][j]\)是不降的,并且增幅逐渐下降

​   

  然后又因为每种钞票是独立的,我们可以考虑一个贪心

  枚举\(n\)张钞票的每一张都选什么,对于每一种钞票\(c\),我们维护一个隐性的\(p_c\)(说是“隐性”是因为在实现的时候你并不需要真的去维护这么一个东西),表示钞票\(c\)当前已经取了\(p_c\)张,那么从贪心的角度来看,我们当前枚举到的这张钞票,肯定希望新加入这张钞票之后,对应的\(g[c]\)的增幅最大,所以就可以得到一个大致的流程:从\(1\)到\(n\)枚举每一张钞票选什么,对于第\(i\)张钞票,\(O(m)\)求得最大的\(g\)的增幅,加入答案,然后对于选择的这个种类\(c\),更新其\(g\)值

​  现在的问题就是怎么维护增幅,为了方便下面只针对确定的\(c\)类钞票进行表述

  一开始的时候\(p_c=0\),\(g[c][0]\)到\(g[c][1]\)的增幅是很好计算的,\(\nabla g[c][1]=1-\prod\limits_{i=1}^n(1-a[i][c])\),但是\(\nabla g[c][2]\)看起来就不能那么直接地进行计算了,所以我们还是看回这个式子:\(\nabla g[i][j]=\sum\limits_{k=j}^mf[i][n][k]=1-\sum\limits_{k=0}^{j-1}f[i][n][k]\),那所以我们只要对于第\(c\)种钞票维护\(f[c][i][j]\)就好,然后维护一个\(sum[c]=\sum\limits_{k=0}^{p_c}f[c][n][k]\),每次更新完\(f[c]\)之后把\(f[c][n][p_c]\)加到\(sum[c]\)里面就好了

​  接下来就是空间怎么解决:对于\(f[c][i][j]\)来说,我们是按照\(j\)进行dp的,显然\(j\)那维可以滚动掉,\(f[c][][j]\)到\(f[c][][j+1]\)的更新是\(O(n)\)的,然后我们就获得了一个\(O(nm)\)的算法

  

  mark:(弱智操作)谁告诉你听算期望的时候可以钦定顺序的???

​  

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=3010,M=310;
double sum[N],f[2][M][N];
double a[N][M];
int now[M],pre[M];
int n,m;
double ans;
void dp(int x){
swap(now[x],pre[x]);
int Now=now[x],Pre=pre[x];
f[Now][x][0]=0;
for (int i=1;i<=n;++i)
f[Now][x][i]=f[Now][x][i-1]*(1-a[i][x])+f[Pre][x][i-1]*a[i][x];
} int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif
int x;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
scanf("%d",&x),a[i][j]=1.0*x/1000;
for (int i=1;i<=m;++i){
f[0][i][0]=1;
for (int j=1;j<=n;++j)
f[0][i][j]=f[0][i][j-1]*(1-a[j][i]);
sum[i]=f[0][i][n];
}
for (int i=1;i<=m;++i) now[i]=0,pre[i]=1;
int which;
double mx;
for (int j=1;j<=n;++j){
mx=0; which=-1;
for (int i=1;i<=m;++i)
if (1-sum[i]>mx)
which=i,mx=1-sum[i];
ans+=mx;
dp(which);
sum[which]+=f[now[which]][which][n];
}
printf("%.10lf\n",ans);
}

最新文章

  1. DDD 领域驱动设计-看我如何应对业务需求变化,愚蠢的应对?
  2. MFC编程入门之二十四(常用控件:列表框控件ListBox)
  3. Asp.net有关访问页面权限的限制和错误页面配置
  4. log4cplus 直接创建logger 对象
  5. lua table序列化和反序列化
  6. 升级xcode7的问题:使用shareSDK,坑的你两眼泪汪汪
  7. loj 1379(最短路变形)
  8. icp算法基本思想
  9. JSP专题
  10. XAML 概述二
  11. What is Object Oriented Design? (OOD)
  12. springmvc的几点见解
  13. 京东笔试---通过考试(DP)
  14. 2017最新最稳定的彩票源码PHP+mysql 新增彩种+全新界面
  15. 简单几步用纯CSS3实现3D翻转效果
  16. 微信小程序支付遇到的坑
  17. LINUX 系统下部署 NFS服务
  18. JQuery跳出each循环的方法
  19. chrome插件离线包下载和安装
  20. 腾讯云centos7.2安装jdk1.7 tomcat7.0部署项目示例

热门文章

  1. SOAPUI使用教程-从现有的服务创建REST模拟服务
  2. Spring声明式事务管理基于@Transactional注解
  3. jsRender 循环for 和props
  4. 【洛谷P3398】仓鼠找sugar
  5. scala的传名参数
  6. Orcle数据库查询练习复习:一
  7. matlab——sparse函数和full函数(稀疏矩阵和非稀疏矩阵转换)
  8. 记一个菜鸟在Linux上部署Tomcat的随笔
  9. 使用Idea编写javaweb以及maven的综合(一)
  10. poj 1486 Sorting Slides(二分图匹配的查找应用)
  11. 各个Maven仓库镜像(包括国内)
  12. 201521123020 《Java程序设计》第6周学习总结
  13. iOS开发针对对Masonry下的FPS优化讨论
  14. Listview嵌套Listview
  15. 日推20单词 Day03
  16. postgres的使用命令
  17. [20170627]使用TSPITR恢复表空间.txt
  18. 洛谷 P1144 最短路计数
  19. PHP中redis的使用
  20. git 使用 添加分支