记录编号	152175	评测结果	AAAAAAAAAA
题目名称	[HAOI 2006]数字序列	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.024 s
提交时间	2015-03-13 14:54:37	内存使用	1.25 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
///==============struct declaration==============

///==============var declaration=================
const int MAXN=35050;
int n;
int f[MAXN],g[MAXN],Arr[MAXN];
int cost[MAXN],ans=0;
vector <int> Seq[MAXN];
///==============function declaration============
int cmp(int a,int b){return a<=b;}
///==============main code=======================
int main()
{

   freopen("sequencec.in","r",stdin);
   freopen("sequencec.out","w",stdout);

   scanf("%d",&n);
   for(int i=1;i<=n;i++){
      scanf("%d",Arr+i);
      Arr[i]-=i;g[i]=INF;
   }
   for(int i=1;i<=n;i++){
      int p=lower_bound(g+1,g+1+n,Arr[i],cmp)-g;
      g[p]=Arr[i];f[i]=p;Seq[p].push_back(i);
      ans=max(ans,f[i]);
   }
   Seq[0].push_back(0);
   printf("%d\n",n-ans);
   n++;f[n]=ans+1;Arr[n]=1000000;
   for(int i=2;i<=n;i++){
      int prev=f[i]-1;cost[i]=INF;
      int siz=Seq[prev].size();
      for(int j=0;j<siz;j++){
         int &e=Seq[prev][j];
         if (e>i) break;
         if (Arr[e]>Arr[i]) continue;
         int prevcost=0,nextcost=0;
         for(int k=e+1;k<=i&&k<n;k++) nextcost+=abs(Arr[k]-Arr[i]);
         cost[i]=min(cost[i],nextcost+cost[e]);
         for(int k=e+1;k<=i&&k<n;k++){///[e+1,k]变为Arr[e]，[k+1,i]变为Arr[i]
            prevcost+=abs(Arr[k]-Arr[e]);
            nextcost-=abs(Arr[k]-Arr[i]);
            cost[i]=min(cost[i],cost[e]+prevcost+nextcost);
         }
      }
   }
   printf("%d\n",cost[n]);
   return 0;
}
///================fuction code====================