Gym - 101190F Foreign Postcards (期望dp)
2024-09-07 02:22:09
题意:有n张标有“C”或“F”的卡片。
1、随机取前k张(1<=k<=n)
2、若这k张的第一张为“C”,则不翻转,否则,全部翻转这k张。
3、然后处理剩下的n-k张
4、重复步骤1~3直至处理完所有卡片。
求处理后卡片W的个数期望。
分析:期望dp从后往前推。
1、对于最后一张卡片,无论为C还是W,最后的结果都是W个数为0,因此dp[len] = 0.
2、对于卡片i,k有(len - i + 1)种选择
若卡片i为C,则前k张卡片是不反转的,预处理前缀和。
k = 1, 1 / (len - i + 1) * (0 + dp[i + 1])
k = 2, 1 / (len - i + 1) * (前两张卡片中W的个数 + dp[i + 2])
.......
k = len - i + 1, 1 / (len - i + 1) * (前len - i + 1张卡片中W的个数)
若卡片i为W,同理也处理处前缀和。
提取公因数1 / (len - i + 1)后,后面的式子合并dp[i + 1] + dp[i + 2] +...+ dp[len]可以边算边处理出后缀和sumsuf[i]。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define lowbit(x) (x & (-x))
const double eps = 1e-8;
inline int dcmp(double a, double b){
if(fabs(a - b) < eps) return 0;
return a > b ? 1 : -1;
}
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 1000000 + 10;
const int MAXT = 10000 + 10;
using namespace std;
char s[MAXN];
LL a1[MAXN], a2[MAXN];
LL sum1[MAXN], sum2[MAXN];
double sumsuf[MAXN], dp[MAXN];
int main(){
freopen("foreign.in", "r", stdin);
freopen("foreign.out", "w", stdout);
scanf("%s", s + 1);
int len = strlen(s + 1);
for(int i = 1; i <= len; ++i){
if(s[i] == 'W') a1[i] = a1[i - 1] + 1;
else a1[i] = a1[i - 1];
}
for(int i = 1; i <= len; ++i){
if(s[i] == 'C') a2[i] = a2[i - 1] + 1;
else a2[i] = a2[i - 1];
}
for(int i = 1; i <= len; ++i){
sum1[i] = sum1[i - 1] + a1[i];
sum2[i] = sum2[i - 1] + a2[i];
}
dp[len] = 0;
sumsuf[len] = 0;
for(int i = len - 1; i >= 1; --i){
LL tmp;
if(s[i] == 'C'){
tmp = sum1[len] - sum1[i - 1] - a1[i] * (len - i + 1);
}
else{
tmp = sum2[len] - sum2[i - 1] - a2[i] * (len - i + 1);
}
dp[i] = (1 / (double)(len - i + 1)) * (sumsuf[i + 1] + tmp);
sumsuf[i] = sumsuf[i + 1] + dp[i];
}
printf("%.12lf\n", dp[1]);
return 0;
}
最新文章
- js图片延迟加载
- 课堂作业二 PAT1025 反转链表
- Win+R命令大全
- tslib1.4与Qt4.8.6的交叉编译与移植
- Java-->;Json解析网页数据
- java 动态创建数据库和动态连接数据库
- 【BZOJ】3038: 上帝造题的七分钟2(线段树+暴力)
- php 命名空间(要求php5.3以上)
- codeforces Codeforces 650A Watchmen
- Array.prototype.map()
- 【转】C/C++ 内存对齐
- [jQuery编程挑战]003 克隆一个页面元素及其相关事件
- c#按键Up和Down对Textbox的内容加1减1
- hdu 5036 Explosion(概率期望+bitset)
- linux-telnet服务配置
- Linux上bash的部分基础特性:
- 关于HTTP协议头域详解
- JSP自定义方法库
- [Python学习笔记] turtle库的基本使用
- Elastic 开发篇 javaAPI(4)
热门文章
- centos6.9下 svn 1.7.10版本 编译安装
- 【PAT甲级】1019 General Palindromic Number (20 分)
- 【转】ERP系统测试方法
- redhat 7.6 常用命令
- 浏览器输入URL后HTTP请求返回的完整过程
- vue中 el [$el] 的理解
- 本周总结(19年暑假)—— Part3
- postgresql shell脚本传递参数并执行sql脚本并
- kafka在zookeeper默认使用/为根目录,将/更换为/kafka
- 一、什么是Velocity及简单示例