2021.12.06 P2501 [HAOI2006]数字序列（动态规划+LIS）

https://www.luogu.com.cn/problem/P2501

题意：

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

求最小的改变次数和此时每个数改变的绝对值之和。

分析：

对于 \(a_i\) ，\(a_j\) ， \(i<j\) ，当 \(j-i<=a_j-a_i\) 时 \(i\) 与 \(j\) 这两项保留。移项得： \(a_i-i<=a_j-j\) ，则第一问转变为求 \(a_i-i\) 的最长不降子序列。在求出来的最长不降子序列中任意相邻两个元素之间的原序列 \(b_i\) 的元素均不在 \(b_k\) 到 \(b_{k+1}\) 中。任取原序列中的 \(k\) ，使 \(i<=k\) 且 \(k<=j\) ，\(suf\) 为从 \(k+1\) 开始到 \(j\) 之间修改的绝对值之和，这些数均被修改为 \(a_j\) ， \(pre\) 为从 \(i\) 开始到 \(k\) 之间修改的绝对值之和，这些数均被修改为 \(a_i\) 。如果存在一个数 \(a_x\) ，且 \(a_x>a_j\) ，则这个数最大可被被修改为 \(a_j\) ，同理，如果存在一个数 \(a_y\) ，且 \(a_y<a_i\) ，那么把 \(a_y\) 修改成 \(a_i\) 更优。但是要保证原序列被修改后依旧是最长不降，所以一定存在某个点使 \(i\) 到 \(j\) 这个区间被分割后形成两层楼梯阶梯，使得修改的绝对值最小。

代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

#define int long long

const int N=4e4+10;

const int inf=0x3f3f3f3f;

int n,a[N],f[N],pre[N],suf[N],fin[N],top,len[N];

int cnt,head[N];

struct node{

	int to,next;

}e[N];

inline void add(int u,int v){

	++cnt;

	e[cnt].to=v;

	e[cnt].next=head[u];

	head[u]=cnt;

}

signed main(){

	IOS;

	cin>>n;

	for(int i=1;i<=n;i++)cin>>a[i],a[i]-=i;

	a[0]=-inf;a[n+1]=inf;

	for(int i=1;i<=n+1;i++){

		int L=0,R=top;

		while(L<R){

			int mid=(L+R+1)>>1;

			if(fin[mid]<=a[i])L=mid;

			else R=mid-1;

		}

		if(L==top)++top;

		len[i]=L+1;

		fin[L+1]=a[i];

		add(len[i],i);

	}

	add(0,0);

	memset(f,inf,sizeof(f));

	f[0]=0;

	for(int i=1;i<=n+1;i++){

		for(int j=head[len[i]-1];j;j=e[j].next){

			int v=e[j].to;

			if(v>i||a[v]>a[i])continue;

			pre[v]=suf[i-1]=0;

			for(int k=v+1;k<i;k++)pre[k]=pre[k-1]+abs(a[k]-a[v]);

			for(int k=i-2;k>=v;k--)suf[k]=suf[k+1]+abs(a[k+1]-a[i]);

			for(int k=v;k<i;k++)f[i]=min(f[i],f[v]+suf[k]+pre[k]);

		}

	}

	cout<<n-top+1<<endl<<f[n+1];

	return 0;

}

巴特西

2021.12.06 P2501 [HAOI2006]数字序列（动态规划+LIS）

2021.12.06 P2501 [HAOI2006]数字序列（动态规划+LIS）

最新文章

热门文章