1049: [HAOI2006]数字序列
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1755 Solved: 756
[Submit][Status][Discuss]
Description
现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。
Input
第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。n<=35000,保证所有数列是随机的
Output
第一行一个整数表示最少需要改变多少个数。 第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。
Sample Input
4
5 2 3 5
Sample Output
1
4
题解
要满足将i+1到j-1的值改变可以构成严格上升序列，那么要满足a[j]-a[i]>=j-i，移项得a[i]-i<=a[j]-j，所以将a[i]-i，然后求a数组的最长不下降子序列，然后用n减去最长不下降子序列长度就是最少改变的数的个数。
因为题目中有负数，所以a[0]=-inf。
设d[i]为将前i个数变成不下降序列的最小代价。
设g[i]为以i结尾的最长不下降子序列长度，那么如果有j<i&&g[j]==g[i]-1&&a[j]<=a[i]，那么说明i可以从j转移过来，如果要改变j+1到i-1的值，那么存在一个k，j<=k<i，满足改变后的值a[j+1]到a[k]等于a[j]，a[k+1]到a[i-1]等于a[i]。
用邻接链表维护g[i]=u的位置，对于第i个点，枚举每个g[j]==g[i]-1的位置j，并且j要满足j<i&&a[j]<=a[i]，再在j到i-1之间枚举k，用两个前缀和维护将j到k的值变成a[j]和a[i]的代价，那么转移方程为：
d[i]=min(d[i],d[j]+sum1[k]+(sum2[i-1]-sum2[k]))。
为了方便处理最后一段，加一个a[++n]=inf。
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define LL long long
using namespace std;
const int N=35005,inf=0x3f3f3f3f;
int n,mx,cnt=1;
int a[N],f[N],g[N],head[N];
LL sum1[N],sum2[N],d[N];
struct edge{
int u,v,next;
}e[N];
void addedge(int u,int v){
e[cnt]=(edge){u,v,head[u]};
head[u]=cnt++;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]-=i;
}
int pos;
a[++n]=inf;
a[0]=-inf;
f[0]=-inf;
for(int i=0;i<=n;i++){
if(a[i]>=f[mx]){
f[++mx]=a[i];
g[i]=mx;
}
else{
pos=upper_bound(f+1,f+mx+1,a[i])-f;
f[pos]=a[i];
g[i]=pos;
}
}
addedge(g[0],0);
for(int i=1;i<=n;i++){
addedge(g[i],i);
d[i]=(1LL<<60);
}
int v;
for(int i=1;i<=n;i++){
for(int j=head[g[i]-1];j;j=e[j].next){
v=e[j].v;
if(v>i||a[v]>a[i])continue;
sum1[v]=sum2[v]=0;
for(int k=v+1;k<i;k++){
sum1[k]=sum1[k-1]+abs(a[k]-a[v]);
sum2[k]=sum2[k-1]+abs(a[k]-a[i]);
}
for(int k=v;k<i;k++){
d[i]=min(d[i],d[v]+sum1[k]+(sum2[i-1]-sum2[k]));
}
}
}
printf("%d
%lld
",n+1-g[n],d[n]);
return 0;
}