文档章节

bzoj 5369: [Pkusc2018]最大前缀和

o
 osc_odyg6b92
发布于 2018/07/13 11:27
字数 558
阅读 13
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

##Description 小C是一个算法竞赛爱好者,有一天小C遇到了一个非常难的问题:求一个序列的最大子段和。 但是小C并不会做这个题,于是小C决定把序列随机打乱,然后取序列的最大前缀和作为答案。 小C是一个非常有自知之明的人,他知道自己的算法完全不对,所以并不关心正确率,他只关心求出的解的期望值, 现在请你帮他解决这个问题,由于答案可能非常复杂,所以你只需要输出答案乘上n!后对998244353取模的值,显然这是个整数。 注:最大前缀和的定义:i∈[1,n],Sigma(aj)的最大值,其中1<=j<=i

##Solution 注意到前缀和的取值只有 $2^n$ 种. 然后可以枚举每一个集合的元素当最大前缀和 , 那么这个集合的元素排列之后每一个后缀都必须大于 $0$ , 且这个集合的补集排列之后必须保证每一个前缀和都小于 $0$. 那么状压 $DP$ 就行了 , 设 $f[i]$ 表示集合 $i$ 作为最大前缀和且排列之后每个后缀都大于 $0$ 的方案数 , $g[i]$ 表示集合 $i$ 中元素排列之后每个前缀都小于 $0$ 的方案数. 强制 $f,g$ 必须在合法的时候才能转移就行了.

#include<bits/stdc++.h>
using namespace std;
const int N=25,mod=998244353;
int f[1<<20],n,a[N],m,g[1<<20],sum[1<<20];
int main(){
  freopen("pp.in","r",stdin);
  freopen("pp.out","w",stdout);
  cin>>n,m=(1<<n)-1;
  for(int i=0;i<n;i++)cin>>a[i];
  for(int i=0;i<n;i++)
	  for(int j=0;j<=m;j++)if(j>>i&1)sum[j]+=a[i];
  for(int i=0;i<n;i++)f[1<<i]=1,g[1<<i]=1;
  for(int i=0;i<=m;i++){
	  if(sum[i]>0){
		  for(int j=0;j<n;j++)
			  if(~i>>j&1)f[i^(1<<j)]=(f[i^(1<<j)]+f[i])%mod;
	  }
	  else{
		  for(int j=0;j<n;j++)
			  if(~i>>j&1)g[i^(1<<j)]=(g[i^(1<<j)]+g[i])%mod;
	  }
  }
  g[0]=1;
  int ans=0;
  for(int i=0;i<=m;i++)
	  if(sum[m^i]<=0)ans=(ans+1ll*f[i]*sum[i]%mod*g[m^i])%mod;
  cout<<(ans+mod)%mod;
  return 0;
}

o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
beego API开发以及自动化文档

beego API开发以及自动化文档 beego1.3版本已经在上个星期发布了,但是还是有很多人不了解如何来进行开发,也是在一步一步的测试中开发,期间QQ群里面很多人都问我如何开发,我的业余时间实在...

astaxie
2014/06/25
2.7W
22
灵活的反向代理和静态资源代理--Goproxy

Goproxy使用代理的方式来加强hosts文件的配置,对hosts文件的修改实时生效(不需要使用firefox上的dns flusher插件),对hosts文件里正常的配置没有任何影响。 通过配置hosts文件中的dns映射,...

weager
2013/06/16
5.6K
0
nginx过滤url实现前台js的配置问题

基于摘要里的,在Java后台实现很方便,只需要读取properties配置文件即可 但是在前台js,js是在浏览器里执行的,无法读取服务器上的配置,除非请求后台,但是每次的开销也是挺大的,所以这个想法被p...

Crazy_Coder
2015/09/24
430
1
一种没有语料字典的分词方法

前几天在网上闲逛,看到一篇美文,说的是怎么在没有语料库的情况下从文本中提取中文词汇,理论部分讲得比较多,但都还是很浅显易懂的,其中涉及一部分信息论的理论,其实只要大学开过信息论这...

wyh817
2016/04/26
406
2
spring-core组件详解——PropertyResolver属性解决器

PropertyResolver属性解决器,主要具有两个功能: 通过propertyName属性名获取与之对应的propertValue属性值(getProperty)。 把${propertyName:defaultValue}格式的属性占位符,替换为实际...

拉风小野驴
2016/05/05
1.9K
0

没有更多内容

加载失败,请刷新页面

加载更多

如何在SQL Server中将多行文本合并为单个文本字符串?

问题: Consider a database table holding names, with three rows: 考虑一个包含名称的数据库表,该表具有三行: PeterPaulMary Is there an easy way to turn this into a single str......

富含淀粉
17分钟前
9
0
在JavaScript中生成特定范围内的随机整数? - Generating random whole numbers in JavaScript in a specific range?

问题: 如何可以生成两个指定的变量之间的随机整数在JavaScript中,例如x = 4和y = 8将输出任何的4, 5, 6, 7, 8 ? 解决方案: 参考一: https://stackoom.com/question/6PRz/在JavaScript中...

fyin1314
47分钟前
8
0
Vim清除最后一个搜索突出显示 - Vim clear last search highlighting

问题: Want to improve this post? 想要改善这篇文章吗? Provide detailed answers to this question, including citations and an explanation of why your answer is correct. 提供此问题......

技术盛宴
今天
23
0
马化腾每天刷 Leetcode?代码你打算写到几岁?

本文作者:o****0 前几天,一张未证真伪的截图流传,图中显示马化腾几乎每天都会在 Leetcode 上提交代码。 截图还贴出一个 Leetcode 账户地址。该地址的头像已从马化腾的照片换成腾讯 logo,...

百度开发者中心
前天
13
0
滴滴 3000+ Kylin Cube 背后的实践经验揭秘

本次分享主要有三个部分:Kylin 在滴滴的整体应用、架构的实践经验、滴滴全局字典最新版本的实现以及 Kylin 最新实时 OLAP 探索经验分享。 Kylin 在滴滴的应用&架构 Kylin 在滴滴的三类应用场...

浪尖聊大数据
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部