分析
考虑最大前缀和满足两个条件,就是所有前缀和都不超过,以及一定有一个等于。
那么就要保证它能达到最大值且一直不能高于它
设 \(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