题解 P10141 [USACO24JAN] Merging Cells P

· · 题解

P10141 题解

题目大意

有 n 个细胞排成一排，第 i 个细胞大小为 c_i，重复 n-1 次，第 i 次从当前的 n-i+1 个细胞中随机选出相邻的两个，并让大的吞噬小的（大小相同右吞左），被吞噬的细胞消失并将大小累加到留下的细胞上。求每个细胞活到最后的概率，对 1e9+7 取模，n\le5000。

题目分析

对于每个细胞单独考虑，设当前考虑的细胞为 i，容易得到 dp_{l,r} 表示 l,r 区间最后活下来的是 i 的概率，转移需要枚举最后一次吞噬。单个细胞复杂度 O(n^3)，总复杂度 O(n^4)，很难优化到 O(n^2)。

上面的做法转移的顺序是合并从小区间到大区间的顺序，正难即反，可以发现如果枚举最后一次合并，则最后留下的细胞必定来自总和较大的区间。也就是说，倒着做把合并变成分裂，每次会确定最后留下的细胞来自左侧的区间还是右侧，并将另一部分舍去不必再考虑。设 dp_{l,r} 表示区间 1,n 经过若干次分裂留下了区间 l,r 的概率。转移时枚举 l\le k<r 表示分裂出 l,k 和 k+1,r，若 sum_{l\sim k}>sum_{k+1\sim r}，则将 dp_{l,k} 加上 \frac{dp_{l,r}}{r-l}，否则让 dp_{k+1,r} 加上后者。直接实现复杂度 O(n^3)。

继续优化，考虑所有能转移到 dp_{l,r} 的区间要不然左端点是 l 要不然右端点是 r。两部分类似，下面只讨论前者。那么如果右端点是 k，则要求 sum_{l,r}>sum_{r+1,k}，容易发现可取的 k 是以 r+1 为左端点的一段区间。这段区间的右端点通过对每一个 l 做双指针是好求的（区间 dp 时通过枚举区间长度从大到小，枚举到的左端点为 l 的区间右端点必然是递减的，随着 r 递减双指针找到最大的 k 即可），则 dp_{l,r} 会加上 \sum_{i=r+1}^k\frac{dp_{l,i}}{i-l}，对每一个 l 维护 \frac{dp_{l,r}}{r-l} 后缀和即可。复杂度 O(n^2)。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5010,mod=1e9+7;
int inv(int a){
    int b=mod-2,r=1;
    while(b){
        if(b&1)r=1ll*r*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return r;
}
void add(int &i,int j){
    i=(i+j>=mod?i+j-mod:i+j);
}
int n;
int s[MAXN],v[MAXN];
int d[MAXN][MAXN],f[MAXN][MAXN],g[MAXN][MAXN],p[MAXN],q[MAXN];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]+=s[i-1];
        v[i]=inv(i);
    }
    d[1][n]=f[1][n]=g[1][n]=v[n-1];
    for(int i=1;i<=n;i++)p[i]=n,q[i]=1;
    for(int h=n-1;h>=1;h--){
        for(int i=1,j=h;j<=n;i++,j++){
            while(s[j]-s[i-1]<=s[p[i]]-s[j])p[i]--;
            add(d[i][j],f[i][j+1]);
            add(d[i][j],mod-f[i][p[i]+1]);
            while(s[j]-s[i-1]<s[i-1]-s[q[i]-1])q[i]++;
            add(d[i][j],g[i-1][j]);
            add(d[i][j],mod-g[q[i]-1][j]);
            if(h>1){
                d[i][j]=1ll*d[i][j]*v[j-i]%mod;
                f[i][j]=f[i][j+1];
                add(f[i][j],d[i][j]);
                g[i][j]=g[i-1][j];
                add(g[i][j],d[i][j]);
            }
        }
    }
    for(int i=1;i<=n;i++)cout<<d[i][i]<<'\n';
    return 0;
}

谢谢观看！