【Luogu P2501】[HAOI2006]数字序列 / 题解

Description

现在我们有一个长度为 n 的整数序列 A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。

求最少的改变数量，和在改变的数最少的情况下，每个数改变的绝对值之和的最小值。

Idea

首先一个套路。

要求严格单调的序列，就先将 $a_i-i$，对处理后的数列 $a’$ 做 $LIS$ 即可。

对于第二问，我们可以区间 $DP$。

枚举 $LIS$ 保留的相邻两个数 $i,j$，它们之间的数一定是前一半和 $a’_i$ 相等，后一半和 $a’_j$ 相等。因为数列随机生成，转移的数量远远到达不了 $\Theta(n^3)$。

Code

#include <bits/stdc++.h>
#define ll long long
#define inf 0x7fffffff
#define maxn 35010
using namespace std;
int read(){
	int x=0,flag=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if (ch=='-') flag=-1,ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
	return x*flag;
}
int len,n,a[maxn],dp[maxn];
ll s[maxn],p[maxn],f[maxn];
vector<int>to[maxn];
ll abss(ll x){return x>0?x:-x;}
int main(){
	n=read();
	for (int i=1;i<=n;++i)
		a[i]=read()-i;
	f[len]=-inf;a[n+1]=inf;
	for (int i=1;i<=n+1;++i){
		if (a[i]>=f[len]) f[++len]=a[i],dp[i]=len;
		else{
			int k=upper_bound(f+1,f+1+len,a[i])-f;
			f[k]=a[i];dp[i]=k;
		}
	}
	printf("%d\n",n-len+1);
	memset(f,0x3f,sizeof(f));f[0]=0;a[0]=-inf;
	for (int i=0;i<=n;++i) to[dp[i]].push_back(i);
	for (int u=1;u<=n+1;++u){
		for (int j=0;j<to[dp[u]-1].size();++j){
			int v=to[dp[u]-1][j];
			if (v>=u||a[v]>a[u]) continue;
			s[v-1]=p[v-1]=0;
			for (int i=v;i<=u;++i)
				s[i]=s[i-1]+abss(a[i]-a[v]),
				p[i]=p[i-1]+abss(a[i]-a[u]);
			for (int k=v-1;k<=u;++k)
				f[u]=min(f[u],f[v]+s[k]-s[v-1]+p[u]-p[k]);
		}
	}
	printf("%lld\n",f[n+1]);
}