注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 1049 数字序列  

2013-10-28 17:12:10|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://pan.baidu.com/share/link?uk=2651016602&shareid=1490516411
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 36000
#define lowbit(p)
using namespace std;
typedef long long LL;
int n,digit[MAXN];
int tot,to[MAXN],next[MAXN],start[MAXN];
void make(int a,int b)
{
tot++;
to[tot]=b;
next[tot]=start[a];
start[a]=tot;
}
void read()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&digit[i]);
digit[i]-=i;
}
}
int Find(int l,int r,int p,int a[])
{
while(l<r)
{
int mid=(l+r)>>1;
if(a[mid]<=p)
l=mid+1;
else
r=mid;
}
return l;
}
void work()
{
static int stack[MAXN],F[MAXN];
static LL g[MAXN],sum1[MAXN],sum2[MAXN];
int top=0;
digit[++n]=1<<30;
stack[++top]=digit[1],F[1]=top;
for(int i=2;i<=n;i++)
{
int id=Find(1,top+1,digit[i],stack);
stack[id]=digit[i],top=max(top,id);
F[i]=id;
}
printf("%d\n",n-F[n]);
for(int i=n;i>=0;i--)
{
g[i]=1LL<<50;
make(F[i],i);
}
g[0]=0,digit[0]=-digit[n];
for(int i=1;i<=n;i++)
for(int j=start[F[i]-1];j;j=next[j])
{
int p=to[j];
if(p>i)
break;
if(digit[p]>digit[i])
continue;
for(int k=p;k<=i;k++)
{
sum1[k]=abs(digit[p]-digit[k]);
sum2[k]=abs(digit[i]-digit[k]);
}
for(int k=p+1;k<=i;k++)
sum1[k]+=sum1[k-1],sum2[k]+=sum2[k-1];
for(int k=p;k<i;k++)
g[i]=min(g[i],g[p]+sum1[k]-sum1[p]+sum2[i]-sum2[k]);
}
cout<<g[n]<<endl;
}
int main()
{
read();
work();
return 0;
}


  评论这张
 
阅读(814)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017