记录编号	382632	评测结果	AAAAAAAAAA
题目名称	[HAOI 2006]数字序列	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2017-03-14 11:26:07	内存使用	1.96 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define mid (l+r)/2
#define LL long long
#define inf 210000000
#define INF 2100000000000000000
const int N=36000;
int n,a[N],top=0,stack[N],f[N],tot=0,point[N],next[N],to[N];
LL g[N],sum1[N],sum2[N];
void add(int x,int y)
{
    tot+=1;
    next[tot]=point[x];
    point[x]=tot;
    to[tot]=y;
}
int abs(int x){return x<0?-x:x;}
int main()
{
  freopen("sequencec.in", "r", stdin);
  freopen("sequencec.out", "w", stdout);
    int i,j,k,l,r,now;
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d",&a[i]),a[i]-=i;
    a[++n]=inf;
    stack[0]=-inf;
    for(i=1;i<=n;++i){
        if(a[i]>=stack[top]) stack[++top]=a[i],f[i]=top;
        else{
            l=1;r=top;
            while(l<=r){
                if(a[i]>=stack[mid]) l=mid+1;
                else r=mid-1;
            }
            stack[l]=a[i];
            f[i]=l;
        }
    }
    printf("%d\n",n-top);
    for(i=n;~i;--i){
        g[i]=INF;
        add(f[i],i);
    }
    a[0]=-inf;
    g[0]=0;
    for(i=1;i<=n;++i)
      for(j=point[f[i]-1];j;j=next[j]){
        now=to[j];
        if(now>i) break;
        if(a[now]>a[i]) continue;
        sum1[now-1]=sum2[now-1]=0;
        for(k=now;k<=i;++k){
            sum1[k]=sum1[k-1]+abs(a[now]-a[k]);
            sum2[k]=sum2[k-1]+abs(a[i]-a[k]);
        }
        for(k=now;k<i;++k)
          g[i]=min(g[i],g[now]+sum1[k]-sum1[now]+sum2[i]-sum2[k]);
      }
    printf("%lld\n",g[n]);
}
/*
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <list>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
#define MAXN 360000
typedef long long LL;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
int a[MAXN];
int stk[MAXN];
int f[MAXN];
LL g[MAXN], sum1[MAXN], sum2[MAXN];
vector<int> G[MAXN];
int main(){
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i++)scanf("%d", a+i);
  for(int i = 1; i <= n; i++){
    a[i] -= i;
   // f[i] = inf;
  }
  int top = 0;
  a[++n] = inf;
  stk[top] = -inf;
  for(int i = 1; i <= n; i++){
    if(a[i] >= stk[top])stk[++top] = a[i], f[i] = top;
    else{
      int l = 1, r = top;
      while(l <= r){
        int mid = (l+r)>>1;
        if(a[i] >= stk[mid])l = mid+1;
        else r = mid-1;
      }
      stk[l] = a[i];
      f[i] = l;
    }
  }
  printf("%d\n", n-top);
  for(int i = n; ~i; i--){
    g[i] = INF;
    G[f[i]].push_back(i);
  }
  a[0] = -inf;
  g[0] = 0;
  for(int i = 1; i <= n; i++){
    for(int j = 0; j < G[f[i]-1].size(); i++){
      int cur = G[f[i]-1][j];
      if(cur > i)break;
      if(a[cur] > a[i])continue;
      sum1[cur-1] = sum2[cur-1] = 0;
      for(int k = cur; k <= i; k++){
        sum1[k] = sum1[k-1]+abs(a[cur]-a[k]);
        sum2[k] = sum2[k-1]+abs(a[i]-a[k]);
      }
      for(int k = cur; k < i; k++)
        g[i] = min(g[i], g[cur]+sum1[k]-sum1[cur]+sum2[i]-sum2[k]);
    }
  }
  printf("%lld\n", g[n]);
  return 0;
}
*/