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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2259][Oibh]新型计算机  

2015-05-19 20:14:07|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2259: [Oibh]新型计算机

Time Limit: 6 Sec  Memory Limit: 128 MB
Submit: 450  Solved: 126
[Submit][Status][Discuss]

Description

Tim正在摆弄着他设计的“计算机”,他认为这台计算机原理很独特,因此利用它可以解决许多难题。 
但是,有一个难题他却解决不了,是这台计算机的输入问题。新型计算机的输入也很独特,假设输入序列中有一些数字(都是自然数——自然数包括0),计算机先读取第一个数字S1,然后顺序向后读入S1个数字。接着再读一个数字S2,顺序向后读入S2个数字……依此类推。不过只有计算机正好将输入序列中的数字读完,它才能正确处理数据,否则计算机就会进行自毁性操作! 
Tim现在有一串输入序列。但可能不是合法的,也就是可能会对计算机造成破坏。于是他想对序列中的每一个数字做一些更改,加上一个数或者减去一个数,当然,仍然保持其为自然数。使得更改后的序列为一个新型计算机可以接受的合法序列。 
不过Tim还希望更改的总代价最小,所谓总代价,就是对序列中每一个数操作的参数的绝对值之和。 
写一个程序: 
? 从文件中读入原始的输入序列; 
? 计算将输入序列改变为合法序列需要的最小代价; 
? 向输出文件打印结果。 

Input

输入文件包含两行,第一行一个正整数N,N<1 000 001。 
输入文件第二行包含N个自然数,表示输入序列。 

Output

仅一个整数,表示把输入序列改变为合法序列需要的最小代价,保证最小代价小于109。 

Sample Input

4 2 2 2 2

Sample Output

1

Solution

暴力从后往前平方DP:f[i]=min(f[j]+|a[i]-(j-i-1)|)

树状数组优化递推,每次以i为下标,分别讨论绝对值正负号插入和查询

Code

/**************************************************************
    Problem: 2259
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:2016 ms
    Memory:25412 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define N 1<<20
typedef long long ll;
int n,i,m;ll tmp,a[N],t1[N],t0[N],a0,a1;
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-48;
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-48;return aa;
}
#define min(a,b) (a<b?a:b)
#define cmin(a,b) (a>b?a=b:1)
void add0(int t,ll f){
    for(;t<=m&&t0[t]>f;t+=t&-t)t0[t]=f;
}
void add1(int t,ll f){
    for(;t<=m&&t1[t]>f;t+=t&-t)t1[t]=f;
}
ll gm0(int t){if(t<=0)return 1LL<<60;if(t>=m)t=m-1;
    for(tmp=1LL<<60;t;t-=t&-t)cmin(tmp,t0[t]);return tmp;
}
ll gm1(int t){if(t<=0)return 1LL<<60;if(t>=m)t=m-1;
    for(tmp=1LL<<60;t;t-=t&-t)cmin(tmp,t1[t]);return tmp;
}
void ins(int i,ll f){
    add0(i,f-i),add1(m-i,f+i);
}
int main(){
    memset(t0,63,sizeof(t0));
    memset(t1,63,sizeof(t1));
    for(n=F(),m=n+2,i=1;i<=n;i++)a[i]=F()+i+1;
    for(ins(n+1,0),i=n;i;i--)a0=gm0(a[i])+a[i],a1=gm1(m-a[i])-a[i],ins(i,min(a0,a1));
    printf("%lld\n",min(a0,a1));
}
  评论这张
 
阅读(122)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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