概率DP好题-[ZJOI2016]线段树-解题报告

· · 题解

学长的博客

都是从暴力DP开始优化起的

设f(v,i,l,r)表示i轮之后，[l,r]内的数\le x，且a[l-1],a[r+1]>x的方案数。

那么转移为

f(v,i,l,r)=f(v,i-1,l,r)g(l,r)+\sum_{j<l}f(v,i-1,j,r)(j-1)+\sum_{j>r} f(v,i-1,l,j)(n-j)

其中g(l,r)为无用操作的数量。

那么答案为

ans[i]=\sum_j val[j](h(i,j)-h(i,j-1))

其中h(i,j)表示位置i的值\le val[j]（val为权值从小到大排序的数组）的方案数：

h(i,j)=\sum_{i\in[l,r]} f(j,m,l,r)

这样直接做貌似是O(n^4)的，但是因为数据随机，所以实际上是O(n^2q)的。

有没有严格的算法呢？答案是有的。

注意到f(v,i,l,r)实际对答案的贡献为f(v,i,l,r)(val[v]-val[v+1])

那么我们可以直接带着总贡献DP，也就是我们设dp(i,l,r)=\sum_v f(v,i,l,r)(val[v]-val[v+1])

实际的转移方程是不变的。

#define N 405
const int inf=1e9;
int n,m;
int a[N];
int dp[2][N][N];
int sdp[2][N][N],tdp[2][N][N];
int g[N][N];
il int C2(int n) {return (LL)n*(n+1)/2%md;}
signed main()
{
#ifdef M207
    freopen("in.in","r",stdin);
    // freopen("ot.out","w",stdout);
#endif
    in(n,m);
    for(ri i=1; i<=n; ++i) in(a[i]);
    a[0]=a[n+1]=inf;
    int cur=0,pre=1;
    for(ri l=1; l<=n; ++l)
    {
        int mx=a[l];
        for(ri r=l; r<=n; ++r)
        {
            ckmax(mx,a[r]);
            if(mx<min(a[l-1],a[r+1]))
                dp[cur][l][r]=(mx-(l==1&&r==n?0:min(a[l-1],a[r+1]))+md)%md;
            g[l][r]=add(C2(l-1),C2(r-l+1),C2(n-r));
        }
    }
    for(ri i=1; i<=m; ++i)
    {
        for(ri l=1; l<=n; ++l)
        {
            for(ri r=l; r<=n; ++r)
                sdp[cur][l][r]=add(sdp[cur][l-1][r],mul(dp[cur][l][r],l-1));
            for(ri r=n; r>=l; --r)
                tdp[cur][l][r]=add(tdp[cur][l][r+1],mul(dp[cur][l][r],n-r));
        }
        swap(cur,pre);
        for(ri l=1; l<=n; ++l)
            for(ri r=l; r<=n; ++r)
                dp[cur][l][r]=add(mul(dp[pre][l][r],g[l][r]),sdp[pre][l-1][r],tdp[pre][l][r+1]);
    }
    for(ri i=1; i<=n; ++i)
    {
        int ans=0;
        for(ri l=1; l<=i; ++l)
            for(ri r=i; r<=n; ++r) inc(ans,dp[cur][l][r]);
        out(ans,' ');
    }
    return 0;
}