P2501 数字序列

第一问需要做一个小转化，

把原序列从a[i]变为a[i]-i，

对这个序列求它的最长不下降子序列，就是最多能够保留的个数

先想想之前的组合数问题:$1\sim{n}$中选$m$个数，每个数可以选多次

转化过程

参考这个转化，我们同样可以对这道题做一些转化：

那么从$n$个数里选$m$个可以重复的数的方案数就是$C(n+m-1,m)$。

如果$i,j$两个数可以选的话，那么肯定满足$a_j-a_i{\ge}j-i$。

因为$j$到$i$有$j-i-1$个数，要严格单调递增，差最小的情况也只能从$a_i$开始依次$+1$。

也就是$a_j-j{\ge}a_i-i$，

所以就回到了组合数的那个问题上了，

所以每个位置减去下标后求一个LIS就可以了。

所以要先用原序列$a$预处理出一个序列$b$，

使得$b[i]=a[i]-i$，

然后求一下$b$的最长不下降的子序列的长度，就是最多能保留的个数，

答案就是$n-$最长不下降子序列的长度。

---

第二问

先求出最长子序列，

对于中间没选的数，

要么比它前面的数小，要么比它后面的数大。

所以如果它比前面的数小，那就把它变为前面的数+1；

如果它比后面的数大，那就把它变为后面的数-1；

这样就可以保证变化的量最小。

我们只要保证$b$是单调不降的就可以。

那么保证$b$是单调不降的代价是多少？

首先b的最长不下降子序列可能有多个，

每个被保留的b[]一定合法，两个被保留的b[]之间的一定不合法，

假设$j$是从$i$转移来的最长上升子序列，也就是在最长上升子序列中它们相邻，

那么$b_j\ge{b_i}$并且$b_j$是满足条件的数中最小的，

假设i~j之间存在一个k，使得$b_j\ge{b_k}$，

那么明显k比i更优，

所以$b_k$要么小于$b_i$要么大于$b_j$。

$b_k\le{b_i}||b_k\ge{b_j}$

所以这之间的数是一定要修改的，

那么怎样修改最优呢？（也就是修改数与原数差的绝对值之和最小），

对于一段连续的区间$l\sim{r}$，

若要加上值的数的个数比要减去值得数的个数要多，

那么让这些数都变成$a_i$最优，因为少数服从多数，改后的值越小对于数量更多而想要变大的数更有利，

相反，如果要加上值的数的个数小于要减去值的个数，

那么让这些数都变成$a_j$最优，

因为改后的值越大对于数量更多而想要变小的数更有利，

若等于，则怎么改绝对值之和都不会改变，

所以像这样不断修改，

最后会变成两段区间，使得左半部分等于$a_i$右半部分等于$a_j$。

所以就可以枚举这个区间中点进行求解。

P2501

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn=35010;
int n,cnt;
int head[maxn],a[maxn],b[maxn],f[maxn],g[maxn],sum1[maxn],sum2[maxn];
struct edge
{
	int to,nxt;
}e[maxn];
void add(int u,int v)
{
	e[++cnt].nxt=head[u];
	head[u]=cnt;//第几条边即代表长度为几的最长上升子序列
	e[cnt].to=v;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]-=i;
	a[++n]=0x3f3f3f3f;a[0]=-0x3f3f3f3f;
	memset(b,0x3f,sizeof(b));
    b[0]=-0x3f3f3f3f,b[1]=a[1];
	int len=1;//初始化
	f[1]=1; 
	for(int i=2;i<=n;i++)//求以所有点为结尾的最长不上升子序列
	{
		int tmp=upper_bound(b,b+len+1,a[i])-b;//返回第一个大于等于a[i]的位置
		len=max(len,tmp);//如果序列中所有元素都比a[i]小，那么就更新长度
		f[i]=tmp;//下标即为最长上升子序列长度
		b[tmp]=a[i];//b中用来存最长上升子序列
	}
	printf("%lld\n",n-len);//第一问答案
	for(int i=0;i<=n;i++) add(f[i],i);//建边，在点与最长上升子序列间建立联系，这里我觉得用vector或者map都可以方便遍历它的前驱
	memset(g,0x3f,sizeof(g));
    g[0]=0;//初始化//g数组代表从1到i闭区间的改变次数最小时改变量之和
	for(int i=1;i<=n;i++)
	{
        //最长上升子序列为i的情况一定从最长上升子序列为i-1的情况转移而来
		for(int j=head[f[i]-1];j;j=e[j].nxt)//枚举从j前驱到j的区间
		{
			int y=e[j].to;//点
			if(y>i||a[y]>a[i]) continue;//虽然长度是当前减一，但是不符合最长不下降子序列的条件，那就跳过
            //下面为枚举k，也就是区间中分界点
			for(int k=y;k<=i;k++) sum1[k]=abs(a[k]-a[y]),sum2[k]=abs(a[k]-a[i]);//sum1为对于区间左端点前缀和 sum2为对于区间右端点后缀和,方便计算所取k的贡献
			for(int k=y+1;k<=i;k++) sum1[k]+=sum1[k-1],sum2[k]+=sum2[k-1];//注意细节从y+1开始枚举
			for(int k=y;k<=i-1;k++) g[i]=min(g[i],g[y]+sum1[k]-sum1[y]+sum2[i]-sum2[k]);//k左边和右边的点分别与左端点和右端点对齐，并取min，此为DP递推式
            //对于每个i都枚举从它的前驱到它之间的区间
		}
	}
	printf("%lld",g[n]);
	return 0;
}