【BZOJ 1049】 1049: [HAOI2006]数字序列 （LIS+动态规划）

1049: [HAOI2006]数字序列

Description

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

Input

　　第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。n<=35000,保证所有数列是随机的

Output

　　第一行一个整数表示最少需要改变多少个数。 第二行一个整数，表示在改变的数最少的情况下，每个数改变
的绝对值之和的最小值。

Sample Input

4
5 2 3 5

Sample Output

1
4

HINT

Source

【分析】　　

　　首先先每个数减去标号，变成<=的问题。

　　第一问显然是LIS。用传统nlogn打法就好了。

　　第二问，明显DP转移方程为：

　　　　　　g[i]=min{g[j]+cost(j,i)|f[j]+1==f[i]}

　　问题还是求cost(j,i)

　　如果满足f[j]+1==f[i],那么中间的元一定要不>=a[i],要不<=a[j]。

　　画个图想一想就知道一定有一个最优解是前半部分等于a[j],后半部分等于a[i]。

　　

　　本来以为这题和上一题BZOJ 1367有异曲同工之妙，事实上这题要简单很多的啊ORZ。。。

　　只要后面好好搞，其实随机数据没有n^3,所以可以过！！、

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 35010
#define INF 0xfffffff
#define LL long long

int a[Maxn],f[Maxn],g[Maxn];
int n;

int myabs(int x) {return x<0?-x:x;}
int mymin(int x,int y) {return x<y?x:y;}
LL mymin(LL x,LL y) {return x<y?x:y;}

int ffind(int l,int r,int x)
{
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(g[mid]<=x) l=mid;
        else r=mid-1;
    }
    return l;
}

void LIS()
{
    int l=0,r=0;
    g[0]=-INF;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=g[r])
        {
            g[++r]=a[i];
            f[i]=r;
        }
        else
        {
            int x=ffind(l,r,a[i]);
            g[x+1]=a[i];
            f[i]=x+1;
        }
    }
    printf("%d
",n-r);
}

struct node
{
    int x,y,next;
}t[Maxn];int len;

int first[Maxn];
void ins(int x,int y)
{
    t[++len].x=x;t[len].y=y;
    t[len].next=first[x];first[x]=len;
}

LL h[Maxn],s1[Maxn],s2[Maxn];

void get_ans()
{
    len=0;
    memset(first,0,sizeof(first));
    for(int i=0;i<=n;i++)
    {
        ins(f[i],i);
    }
    memset(h,127,sizeof(h));
    h[0]=0;
    for(int i=1;i<=n;i++)
     for(int j=first[f[i]-1];j;j=t[j].next)
     {
         int y=t[j].y;
         if(y>i) continue;
         if(a[y]>a[i]) continue;
         s1[y]=0;
         for(int k=y+1;k<i;k++) s1[k]=s1[k-1]+myabs(a[k]-a[y]);
         s2[i]=0;
         for(int k=i-1;k>y;k--) s2[k]=s2[k+1]+myabs(a[k]-a[i]);
         for(int k=y;k<i;k++) h[i]=mymin(h[i],h[y]+s1[k]+s2[k+1]);
     }
    printf("%lld
",h[n]);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) a[i]-=i;
    a[0]=-INF;a[++n]=INF;
    LIS();
    get_ans();
    return 0;
}

2017-01-17 10:33:31