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

首先可以计算出每个区间选入答案的代价，然后考虑到答案区间不交，问题变为选出若干个长度为

L

的不交区间，最小化代价和。

打表可以发现答案对选出区间数量存在凸性。

为什么呢，观察用来打表的 dp，即

dp_{i,j}

表示考虑

[1,i]

选出

j

个区间的代价，你发现

dp_{i,j}

的转移形如先把

dp_{i-1,j}

复制过来，再把

dp_{i-k,j}

向右上平移后与其取

\min

，假若

dp_{p,j}

在

p<i

时存在凸性，那么两个上凸壳在做平移和取

\min

操作后仍然是一个上凸壳，故

dp_{i,j}

也是凸的，所以我们可以向下归纳证明凸性存在。

对于任意一个子区间显然也都存在凸性，考虑对序列分治，分治的过程中维护

f_{i,j,k}

表示选出的最左边和最右边的区间距离区间端点的距离分别为

i,j

的情况下，选出

k

个区间最小化代价之和，合并就直接闵可夫斯基和，时间复杂度

O(L^3 n \log n)

。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int L,n;
const int maxn = 3e5+114;
const int inf = 1e18;
char S[maxn];
int c[maxn];
struct info{
    vector<int> dp[3][3];//0 1 2 | 0 1 2
    info(){
        for(int i=0;i<L;i++)
            for(int j=0;j<L;j++) dp[i][j].push_back(0);
    }
};
vector<int> merge(vector<int> a,vector<int> b){
    vector<int> da,db;
    for(int i=1;i<(int)a.size();i++) da.push_back(a[i]-a[i-1]);
    for(int i=1;i<(int)b.size();i++) db.push_back(b[i]-b[i-1]);
    vector<int> dc;
    dc.push_back(a[0]+b[0]);
    int ta=0,tb=0;
    while(ta<(int)da.size()||tb<(int)db.size()){
        if(ta<(int)da.size()&&tb<(int)db.size()){
            if(da[ta]<db[tb]){
                dc.push_back(da[ta]);
                ta++;
            }else{
                dc.push_back(db[tb]);
                tb++;
            }
        }else if(ta<(int)da.size()){
            dc.push_back(da[ta]);
            ta++;
        }else{
            dc.push_back(db[tb]);
            tb++;
        }
    }
    for(int i=1;i<(int)dc.size();i++) dc[i]+=dc[i-1];
    /*
    cout<<"merge ----------------------\n";
    for(int x:a) cout<<x<<' ';
    cout<<'\n';
    for(int x:b) cout<<x<<' ';
    cout<<'\n';
    for(int x:dc) cout<<x<<' ';
    cout<<'\n';*/
    return dc;
}
vector<int> min(vector<int> a,vector<int> b){
    if(a.size()>b.size()) swap(a,b);
    for(int i=0;i<a.size();i++) b[i]=min(b[i],a[i]);
    return b;
}
void work(info &x){
    for(int i=L-1;i>=1;i--){
        for(int j=0;j<L;j++){
            x.dp[i-1][j]=min(x.dp[i-1][j],x.dp[i][j]);
        }
    }
    for(int j=L-1;j>=1;j--){
        for(int i=0;i<L;i++){
            x.dp[i][j-1]=min(x.dp[i][j-1],x.dp[i][j]);              
        }
    }    
}
int W[maxn];
int w(int p){
    int res=0;
    res+=(S[p]!='M')?c[p]:0;
    for(int i=1;i<=L-1;i++){
        res+=(S[p+i]!='O')?c[p+i]:0;
    }   
    return res;
}
info solve(int l,int r){
    if(r-l+1<2*L){
        info res=info();
        for(int i=0;i<L;i++){
            int lt=l+i;
            if(lt+L-1<=r) res.dp[i][r-(lt+L-1)].push_back(W[lt]);
        }
        work(res);
        return res;
    }
    int mid=(l+r)>>1;
    info ldp=solve(l,mid),rdp=solve(mid+1,r);   
    info res=info();
    for(int i=0;i<L;i++){
        for(int j=0;j<L;j++) res.dp[i][j]=merge(ldp.dp[i][0],rdp.dp[0][j]);
    }
    for(int i=0;i<L;i++){
        for(int j=0;j<L;j++){
            for(int k=1;k<L;k++){
                res.dp[i][j]=min(res.dp[i][j],merge(merge(ldp.dp[i][k],rdp.dp[L-k][j]),{0,W[mid-k+1]}));
            }
        }
    }
    work(res);
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>L>>n;
    for(int i=1;i<=n;i++) cin>>S[i];
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i+L-1<=n;i++) W[i]=w(i);
    info dp=solve(1,n);
    for(int i=1;i<=(n/L);i++) cout<<dp.dp[0][0][i]<<'\n';
    return 0;
}

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

文章操作

相关推荐

评论

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