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

CPP

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);
}

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

文章操作

Sol

Code

相关推荐

评论

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