题解 CF1810G The Maximum Prefix

tzc_wk · 2023-04-18 18:47:00 · 题解

挺小清新的一道计数题。

首先先分析下这个“最大前缀和”，按照最朴素的思路就是扫一遍每个前缀，然后记录一下当前的 sum 与前面的 mx，但是如果你一直陷在这个思路上你就似了，因为按照这个思路做，你 DP 状态里需要记录 sum 和 mx 两个维度，算上下标一维总共是 n^3，并且没有任何办法省掉当中任何一个循环，所以哪怕解决 k=n 的问题都至少需要 O(n^3)。

考虑换一个角度处理这个“最大前缀和”，我们倒着 DP，f_i 表示 [i,n] 后缀的最大前缀和，显然 f_i=\max(f_{i+1}+a_i,0)。这样的好处一目了然：我们倒着 DP 的时候，只用记录一个维度也就是当前位置的 f_i，于是 k=n 的情况就迎刃而解了：dp_{i,j} 表示考虑到 i，目前 f_i=j 的概率。

但是还有一个问题，就是我们对 k=1,2,3,\cdots,n 求答案，相当于每次在末尾加一个数，这就导致我们 DP 状态不得不重新计算，而每次重新计算复杂度又变成了三方。这个 bug 的修补方法也比较 trivial，倒着 DP 行不通，我们就再改回正着 DP 呗。我们将 DP 状态改为：设 dp_{i,j} 表示当前在 i，在已知 f_{i+1}=j 的情况，随机填 [1,i] 的前缀，得分的期望值。考虑这样的转移：

• 如果 j\ne 0：
  • dp_{i,j}·a_{i+1}\to dp_{i+1,j-1}
  • dp_{i,j}·(1-a_{i+1})\to dp_{i+1,j+1}
• 如果 j=0：
  • dp_{i,j}·(1-a_{i+1})\to dp_{i+1,0}
  • dp_{i,j}·(1-a_{i+1})\to dp_{i+1,1}

初值 dp_{0,i}=h_i，最终所求即为 dp_{i,0}。

代码非常短：

const int MAXN=5000;
const int MOD=1e9+7;
int qpow(int x,int e){int ret=1;for(;e;e>>=1,x=1ll*x*x%MOD)if(e&1)ret=1ll*ret*x%MOD;return ret;}
int n,a[MAXN+5],dp[MAXN+5][MAXN+5];
void solve(){
    scanf("%d",&n);
    for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)dp[i][j]=0;
    for(int i=1,x,y;i<=n;i++)scanf("%d%d",&x,&y),a[i]=1ll*x*qpow(y,MOD-2)%MOD; 
    for(int i=0;i<=n;i++)scanf("%d",&dp[0][i]);
    for(int i=0;i<n;i++)for(int j=0;j<=n;j++){
        if(j){
            dp[i+1][j-1]=(dp[i+1][j-1]+1ll*a[i+1]*dp[i][j])%MOD;
            if(j<n)dp[i+1][j+1]=(dp[i+1][j+1]+1ll*(1-a[i+1]+MOD)*dp[i][j]%MOD);
        }else{
            dp[i+1][0]=(dp[i+1][0]+1ll*(1-a[i+1]+MOD)*dp[i][j])%MOD;
            dp[i+1][1]=(dp[i+1][1]+1ll*(1-a[i+1]+MOD)*dp[i][j])%MOD;
        }
    }
    for(int i=1;i<=n;i++)printf("%d%c",dp[i][0]," \n"[i==n]);
}
int main(){
    int qu;scanf("%d",&qu);while(qu--)solve();
    return 0;
}