题解：P11459 [USACO24DEC] It's Mooin' Time P

LastKismet · 2025-07-07 20:05:53 · 题解

Sol

记 f_i 表示使存在 i 个要求区间的最小代价，不难发现 f 是有单调性的。

考虑对序列分治，合并时除了两边的答案整合更新，还需要额外考虑跨越中界的新块。

先说两边答案整合更新吧，其实就是 Min-Add 卷积，直接闵可夫斯基和优化即可。

考虑中间的情况，发现 L 很小，我们额外开两维状态，维护两个边界距最近的被选中字符串的距离。这个可以顺手后缀取 \min 一下。合并时令中间空出足够一个新区间的长度并更新相应答案即可。具体实现可以参考代码。

除此之外就没什么了，预处理区间贡献是简单的。

注意为了方便代码中重载了多项式 +=。

Code

int len,n;
string s;
ll c[N],b[N];
struct node{
    vec<ll> v[L][L];
    node(){rep(i,0,2)rep(j,0,2)v[i][j].resize(1,0);}
};
inline void operator+=(vec<ll> &a,const vec<ll> &b){
    if(a.size()<b.size())a.resize(b.size(),INF);
    repl(i,0,b.size())chmin(a[i],b[i]);
}
inline vec<ll> mincowski(vec<ll> a,vec<ll> b){
    per(i,a.size()-1,1)a[i]-=a[i-1];
    per(i,b.size()-1,1)b[i]-=b[i-1];
    vec<ll> c(a.size()+b.size()-1);
    merge(a.begin()+1,a.end(),b.begin()+1,b.end(),c.begin()+1);
    c[0]=a[0]+b[0];
    repl(i,1,c.size())c[i]+=c[i-1];
    return c;
}

node solve(int l,int r){
    node res;
    if(r-l+1<(len<<1)){
        rep(i,0,r-l+1-len)res.v[i][r-(l+i+len-1)].resize(2,b[l+i]);
    }else{
        int m=l+r>>1;
        node lres=solve(l,m),rres=solve(m+1,r);
        repl(lf,0,len)repl(rt,0,len){
            res.v[lf][rt]+=mincowski(lres.v[lf][0],rres.v[0][rt]);
            rep(k,1,len-1)res.v[lf][rt]+=mincowski(mincowski(lres.v[lf][k],rres.v[len-k][rt]),{0,b[m-k+1]});
        }
    }
    per(i,len-1,1)repl(j,0,len)res.v[i-1][j]+=res.v[i][j];
    per(j,len-1,1)repl(i,0,len)res.v[i][j-1]+=res.v[i][j];
    return res;
}

inline void Main(){
    read(len,n,s);s=" "+s;
    rep(i,1,n)read(c[i]);
    rep(i,1,n-len+1){
        b[i]=(s[i]!='M')*c[i];
        repl(j,1,len)b[i]+=(s[i+j]!='O')*c[i+j];
    }
    auto f=solve(1,n);
    rep(k,1,n/len)put(f.v[0][0][k]);
}