bzoj 1049: [HAOI2006]数字序列

Description

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

但是不希望改变过多的数,也不希望改变的幅度太大。

solution

正解:DP
这题相当诡异.
首先是一个套路,转化严格递增为不降,我们只需要把序列中的每一个元素都变为 (a[i]-i),设新数组为 (b[i]).
我们要改变的尽量少,就要使得不改变的尽量多,设 (f[i]) 表示前(i)个已经改变好,不改变数的最小值.
原数组 (a[i]) 的话,转移为 (f[i]=Max(f[j]+1)),需要满足 (a[i]-a[j]>=i-j).
对于新数组,我们只需要满足不降即可,所以 (b[j]<=b[i]),那么第一问我们可以转化为最长不降子序列,(O(nlogn)) 可以求出

对于第二问,我们设 (g[i]) 表示前(i)已经处理好的最小费用,(g[i]=g[j]+w[j+1][i])(j) 满足 (f[i]=f[j]+1),我们可以挂链转移
我们需要猜一个结论:(w[j][i]) 的最优情况一定是存在一个 (k) (i<k<j) 使得 (j-k) 全部变为 (b[j])(i-k)全部变为 (b[i]).
可以感性证明:前面的要选的位置尽量低,因为如果前面的选的很高,那么后面的一堆都要变化这么多,显然不会更优.
我们枚举断点转移即可,复杂度 (O(n^3)) 但是随机数据下跑得过,十分玄学

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=35005;
const ll inf=2e16;
ll a[N];int n,f[N];ll h[N];ll g[N],s1[N],s2[N];
il int midit(RG int l,RG int r,ll x){
   RG int mid,ret=0;
   while(l<=r){
      mid=(l+r)>>1;
      if(h[mid]<=x)ret=mid,l=mid+1;
      else r=mid-1;
   }
   return ret;
}
void solve1(){
   int t;
   a[++n]=1<<30;
   for(int i=1;i<=n;i++)h[i]=2e9+10;
   h[1]=a[1];f[1]=1;
   for(int i=2;i<=n;i++){
      t=midit(1,n,a[i]);
      f[i]=t+1;
      h[f[i]]=Min(h[f[i]],a[i]);
   }
   printf("%d
",n-f[n]);
}
int num=0,head[N],to[N],nxt[N];
il void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}
void solve2(){
   for(int i=n;i>=0;i--)link(f[i],i),g[i]=inf;
   g[0]=0;a[0]=-a[n];
   for(int i=1;i<=n;i++){
      for(int l=head[f[i]-1];l;l=nxt[l]){
         int j=to[l];if(j>i)break;
         if(a[j]>a[i])continue;
         for(int k=j;k<=i;k++){
            s1[k]=abs(a[j]-a[k]);
            s2[k]=abs(a[i]-a[k]);
         }
         for(int k=j+1;k<=i;k++)
            s1[k]+=s1[k-1],s2[k]+=s2[k-1];
         for(int k=j;k<i;k++)
            g[i]=Min(g[i],g[j]+s2[i]-s2[k]+s1[k]-s1[j]);
      }
   }
   printf("%lld
",g[n]);
}
void work()
{
   scanf("%d",&n);
   for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]-=i;
   solve1();solve2();
}

int main()
{
	work();
	return 0;
}

原文地址:https://www.cnblogs.com/Hxymmm/p/7751595.html