CF1810G 做题记录

· · 个人记录

分析

首先考虑一个暴力 DP，即设 f_{i,j,k} 表示枚举到第 i 个数，当前前缀和为 j ，最大前缀和为 k 的方案数，转移因为只有 1 和 -1 可选，是 O(1) 的，复杂度 O(n^3)。

我们发现把 j 和 k 这两维记录下来会导致状态十分冗余。

考虑另一种计算最大前缀和的方法，类似 PKUSC2018 最大前缀和，我们发现一个前缀是最大前缀和，当且仅当去掉这个前缀后，剩下的序列的任意前缀和都小于等于 0，否则移到那个大于 0 的位置更优。

于是设 sum_i 为 i 处最大前缀和有倒序推导的方法 sum_i=\max(sum_{i+1},0)+a_i。

如此我们就可以正常推导了，设 f_{i,j} 表示 [i+1,n+1] 区间内最大前缀和为 j 时的期望，初始值为 f_{0,j}=h_j。

转移考虑第 i 个位置选的数，有

f_{i,j}=p_i\times f_{i-1,j+1}+(1-p_i)\times f_{i-1,\max(j-1,0)}

每个 k 的答案即 f_{k,0}，相当于 k 后面没有数。

推最大前缀和的方法是倒着来的，而本题倒着推导期望，所以实际上是正着 DP。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5010;
const int mod = 1e9+7;
ll qpow(ll a,ll b){
    ll res=1;
    for (; b; b>>=1){
        if (b&1) res=res*a%mod;
        a=a*a%mod;
    }
    return res;
}
ll f[N][N];
ll w[N], p[N];
ll ans[N];
void solve(){
    int n; cin>>n;
    for (int i=1;i<=n;++i){
        int x,y; cin>>x>>y; p[i]=1ll*x*qpow(y,mod-2)%mod;
    }
    for (int i=0;i<=n;++i) cin>>w[i];
    for (int i=0;i<=n+1;++i){
        for (int j=0;j<=n+1;++j) f[i][j]=0;
    }
    for (int i=0;i<=n;++i) f[0][i]=w[i];//[1,n]的前缀和为i 时的贡献为wi
    for (int i=1;i<=n;++i){
        for (int j=0;j<=n;++j){
            f[i][j]=(p[i]*f[i-1][j+1]%mod+(mod+1ll-p[i])*f[i-1][max(j-1,0)]%mod)%mod;
        }
        printf("%d ",f[i][0]);
    }
    puts("");
}
int main(){
    int t; cin>>t;
    while(t--) solve();
}