文档章节

BZOJ4318 OSU!

o
 osc_1ee7cxmx
发布于 2018/08/06 18:11
字数 324
阅读 11
收藏 0

精选30+云产品,助力企业轻松上云!>>>

[TOC]

###BZOJ4318 OSU! 题目传送门

###题解 一道比较简单的期望$Dp$。我们记$f[i]$为到第$i$位时的期望分数,$g[i]$为期望长度,分析一下转移我们可以发现连续1的长度从$x-1$变成$x$时,贡献变化为$f[i]=f[i-1]+(3g[i−1]^2+3g[i−1]+1)*a[i]$。所以我们可以记$g1[i]$表示到第$i$位时的期望长度的平方,$g2[i]$为期望长度。每次转移的时候同时更新这两个值。 ###code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=1e5+500;
int n;
double x;
double f[maxn],g1[maxn],g2[maxn];
/*==================Define Area================*/
int main() {
	read(n);
	for(int i=1;i<=n;i++) {
		scanf("%lf",&x);
		g1[i]=(g1[i-1]+1)*x;
		g2[i]=(g2[i-1]+2*g1[i-1]+1)*x;
		f[i]=f[i-1]+(3*g2[i-1]+3*g1[i-1]+1)*x;
	}
	printf("%.1lf\n",f[n]);
	return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

我们一定会在人生的更高处相见的

2020.6.7 我知道没人会看到 2021.6.7 我再来写下 每天进步一点点 一年后我就是不一样的我 你也是。 高考加油!

osc_9oidllr2
32分钟前
16
0
esp8266物联网开发一:MicroPython初战江湖

用esp8266做的物联网开发,涉及到固件烧写,固件擦除,代码编写等方面,做一一记录。 1. 固件烧写 首先,下载固件烧写工具:https://www.espressif.com/sites/default/files/tools/flash_dow...

osc_s2b5kacl
33分钟前
20
0
获小黄衫有感

这个作业属于哪个课程 https://edu.cnblogs.com/campus/fzu/2020SpringW/ 一、与软工的开始 在选课的时候咨询学长意见,听上届学长说这门课会有寒假作业,心里很忐忑,又抱有侥幸心理——可能...

osc_r5t7sskd
35分钟前
9
0
ppt 视频不显示控制条

1 正常解决方法 2 如果还不能显示可能是ppt是兼容模式,另存为非兼容模式就好了 后缀是.ppt 现存就好了

osc_hzf6peqc
36分钟前
15
0
五笔经常打不出来的字:温故而知新

遍 ynmp 凸凹 hgmm 凸 hgm 凹mmgd

osc_iy56i6w3
38分钟前
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部