题解：P10197 [USACO24FEB] Minimum Sum of Maximums P

LastKismet · 2025-11-20 14:22:37 · 题解

Sol

首先有一个 trick 就是 \max(a,b) 可以表示为 \frac{a+b+|a-b|}{2}。故而我们只需要最小化 \sum\limits_{i=1}^{N-1}|a_i-a_{i+1}|。

然后考虑 K 个固定的瓷砖，可以视作他们把原序列分成了若干段。

观察，不难想到各段内部显然是升序或降序填数的。故而总贡献可以视作：

\sum |L-mn|+mx-mn+|R-mx|

其中 L,R 为这一段两端固定点的较小值与较大值，mn,mx 为这一段里填的非定值的最小值与最大值。

继续观察，发现随着 mn,mx 各自增大，|L-mn|-mn 不增、|R-mx|+mx 不降。故而可以得出，每一段填的数不会有相交关系，要么不交要么包含，且小段的值域区间内不会有数给包含它的大段。

于是考虑区间 DP，发现段数很小可以状压，于是 f(l,r,S) 表示使用值域上 [l,r] 的数填满了 S 中的区间的最小代价。转移只有三种（\gets 表示取较小值操作）：

在一侧预留一个数给包含它的区间，f(l,r,S)\gets \min(f(l+1,r,S),f(l,r-1,S))。
把两段拼接起来，f(l,r,S\cup T)\gets\min f(l,k,S)+f(k+1,r,T)。
在外面套一个区间，要求 sz_x= r-l+1-sz_S，f(l,r,S\cup\{x\})\gets f(l+1,r-1,S)+|L_x-l|+r-l+|R_x-r|。

细节上，给区间最两侧额外加两个 10^6 的定点以方便 DP，最后减去贡献即可。

Code

const int N=305,K=7;

int n,k,m;
int a[N],x[N],cnt[N];
int p[K+1],g[N];
int sm;
int L[K],R[K],sz[1<<K];
int f[N][N][1<<K];

inline int gv(int l,int r,int k){return abs(x[l]-L[k])+x[r]-x[l]+abs(x[r]-R[k]);}

inline void Main(){
    cin>>n>>k;
    rep(i,1,n)cin>>a[i];
    rep(i,1,n)sm+=a[i]*2;
    rep(i,1,k)cin>>p[i],g[p[i]]=1;
    rep(i,1,n)if(!g[i])x[++m]=a[i];
    sort(x+1,x+1+m);
    rep(i,1,n)if(!g[i])a[i]=lower_bound(x+1,x+1+m,a[i])-x,a[i]+=(cnt[a[i]]++);
    a[0]=1e6,a[n+1]=1e6;
    int kkk;
    p[kkk=k+1]=n+1;k=0;
    rep(i,1,kkk){
        if(p[i]==p[i-1]+1)sm+=abs(a[p[i]]-a[p[i-1]]);
        else L[k]=min(a[p[i]],a[p[i-1]]),R[k]=max(a[p[i]],a[p[i-1]]),sz[1<<k]=p[i]-p[i-1]-1,++k;
    }
    repl(s,1,1<<k)sz[s]=sz[s^s&-s]+sz[s&-s];
    memset(f,0x3f,sizeof f);
    repl(i,0,k)rep(l,1,m-sz[1<<i]+1)f[l][l+sz[1<<i]-1][1<<i]=gv(l,l+sz[1<<i]-1,i);
    repl(s,1,1<<k)rep(l,sz[s],m)rep(i,1,m-l+1){
        int j=i+l-1;
        chmin(f[i][j][s],min(f[i+1][j][s],f[i][j-1][s]));
        for(int t=s-1&s;t;t=t-1&s)chmin(f[i][j][s],f[i][i+sz[t]-1][t]+f[i+sz[t]][j][s^t]);
        if(sz[s]==l)repl(x,0,k)if(s>>x&1)chmin(f[i][j][s],f[i+1][j-1][s^1<<x]+gv(i,j,x));
    }
    sm+=f[1][m][(1<<k)-1]+2e6;
    put(sm/2-(int)2e6);
}