首页 > 其他分享 >#期望dp#CF1810G The Maximum Prefix

#期望dp#CF1810G The Maximum Prefix

时间:2023-10-28 22:23:01浏览次数:41  
标签:int 最大值 CF1810G Prefix ans dp mod

洛谷题面
CF1810G


分析

考虑最大前缀和满足两个条件,就是所有前缀和都不超过,以及一定有一个等于。

那么就要保证它能达到最大值且一直不能高于它

设 \(dp[i][j][0/1]\) 表示前 \(i\) 个数离达到最大值还需要 \(j\) 且未/已经达到过最大值。

初始化就是 \(dp[0][j][j==0]=h[j]\),然后转移就是看 \(j\) 减到零的话第三维就为一,就不断加一减一。

对于每个 \(i\) 输出 \(\sum_{j=0}^{n}dp[i][j][1]\),因为末尾不一定要达到最大值,所以可以为任意值,只要达到过即可


代码

#include <cstdio>
#include <cctype>
using namespace std;
const int N=5011,mod=1000000007;
int n,p[N],dp[N][2],f[N][2],ans;
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans;
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
int ksm(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=1ll*x*x%mod)
	    if (y&1) ans=1ll*ans*x%mod;
	return ans;
}
void Mo(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
int main(){
	for (int T=iut();T;--T){
		n=iut();
		for (int i=1;i<=n;++i){
			int x=iut(),y=iut();
			p[i]=1ll*x*ksm(y,mod-2)%mod;
		}
		for (int i=0;i<=n;++i) dp[i][i==0]=iut();
		for (int i=1;i<=n;++i){
			ans=0;
			for (int j=0;j<=n;++j)
			for (int k=0;k<2;++k) f[j][k]=dp[j][k],dp[j][k]=0;
			for (int k=0;k<2;++k){
				for (int j=0;j<n;++j) Mo(dp[j][k|(j==0)],1ll*f[j+1][k]*p[i]%mod);
				for (int j=1;j<=n;++j) Mo(dp[j][k],f[j-1][k]*(mod+1ll-p[i])%mod);
			}
		    for (int j=0;j<=n;++j) Mo(ans,dp[j][1]);
			print(ans),putchar(i==n?10:32);
		}
		for (int j=0;j<=n;++j)
		for (int k=0;k<2;++k)
		    dp[j][k]=f[j][k]=0;
	}
	return 0;
}

标签:int,最大值,CF1810G,Prefix,ans,dp,mod
From: https://www.cnblogs.com/Spare-No-Effort/p/17794774.html

相关文章

  • FreeSWITCH添加自定义endpoint之api及app开发
    操作系统:CentOS7.6_x64FreeSWITCH版本:1.10.9之前写过FreeSWITCH添加自定义endpoint的文章,今天整理下api及app开发的笔记。历史文章可参考如下链接:FreeSWITCH添加自定义endpointFreeSWITCH添加自定义endpoint之媒体交互一、常用函数介绍这里列举下开发过程中常用的函数。1......
  • 一张图搞懂远程桌面多用户支持软件:RDPWrapper里的single session pre user
    Windows系统实例默认只允许单个用户连接一个远程桌面会话,如果已存在一个远程桌面会话,当另一个远程桌面会话连接时会移除之前的远程桌面会话。但是勾了这个singlesessionpreuser,为每个用户创建一个独立会话。就会出现:可以同一个用户,多个桌面窗口的情况。缺少是:接不上同一帐号......
  • DP技巧与DP杂题
    DP常用技巧增加维数交换答案与状态可行解转最优解删掉本质相同的状态对部分状态\(dp\)遇到转移顺序的困难,考虑记忆化搜索遇到转移细节过多的问题,考虑从\(i\rightarrowi+1\)而不是\(i-1\rightarrowi\)考虑状态时,先把需要记下来的都记一遍,再考虑优化DP杂题CF83......
  • 树形dp
    P3174[HAOI2009]毛毛虫(树的直径变式)题目对于一棵\(N\)\((N\le3\times10^5)\)个点的树,我们可以将某条链和与该链相连的边抽出来,看上去就象成一个毛毛虫。求点数最多的毛毛虫题解本题与树的直径的求法非常类似设\(f_u\)表示以\(u\)为头的毛毛虫的最大点数那么转......
  • 状态压缩dp
    相关技巧枚举子集:如果一个集合状态\(S\)由其所有子集\(S0\subsetneqS\)转移得到,这样转移的时间复杂度为\(\sum\limits_{i=0}^n\dbinomni2^i=3^n\)for(intS0=S;S0;S0=(S0-1)&S){{ ...}高维前缀和考虑二维前缀和还可以怎么计算:对于每一维,......
  • 数位dp
    数位dp的一般套路问题形式给你一个条件\(A\),然后询问值大小在\([L,R]\)中有多少满足条件的数这个问题暴力去做一般是\(\mathcal{O}(R)\)的时间复杂度,但是通过数位dp我们可以把这个东西优化到\(\mathcal{O}(\log_{10}R)\)求解过程首先我们将区间\([L,R]\)的限制利......
  • 矩阵快速幂优化dp
    寻址连续优化for(inti=1;i<=n;i++)for(intk=1;k<=n;k++)if(a.a[i][k])for(intj=1;j<=n;j++)c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%mod;P3216[HNOI2011]数学作业(普通套路)题目......
  • #dp,二项式反演,容斥#CF285E Positions in Permutations
    题目问有多少个长度为\(n\)的排列\(P\)满足\(|P_i-i|=1\)的\(i\)的个数恰好为\(k\)个分析设\(dp_{i,j,k}\)表示前\(i\)个数钦定\(j\)个数满足上述条件且现在\(i\)和\(i+1\)因此被占用的方案数。那么第\(i\)个满足上述条件无非就是放入\(i-1\)或者\(......
  • cloudpickle pickle 扩展包
    pickle是python的序列化包,但是默认pickle不能进行lambda的处理,cloudpickle对于pickle进行了一些扩展,可以更好的支持集群节点之间的共享以及计算,同时apachespark的pyspark也集成了此功能,只是是自己fork的完整代码参考使用dump.py importcloudpickle,picklesquaredv2......
  • CentOS7系统放行TCP/UDP端口教程
    在使用CentOS7操作系统时,您需要放行某些端口,以便应用程序能够正常运行。下面是如何放行TCP/UDP端口的步骤。步骤1:SSH连接服务器使用SSH方式连接服务器,如果您不知道如何SSH连接服务器,可以查看该教程:SSH远程连接Linux服务器教程步骤2:确定要放行的端口在放行端口之前,您需要确定要......