题目:http://www.lydsy.com/JudgeOnline/problem.php?id=3427

可以证明最终序列为-1...0....1

因为首先如果 a(i-1) 为-1或0,执行操作不会让答案变优。

然后,如果可以加到大于1的某个数字,一定可以加到1,显然加到1更佳。

然后简单dp,f[i][j]表示第i位为j的最少步数。

#include <cstdio>
#include <cstring>
#include <algorithm> #define N 1000010 using namespace std; int f[N][],n,a[N]; int min(int a,int b,int c,int d){
return min(min(a,d),min(b,c));
} int min(int a,int b,int c){
return min(a,min(b,c));
} int calc(int x,int to,int v){
v--;
if(x==to) return ;
if(x+v==to) return ;
if(x+*v==to) return ;
return 0x3f3f3f3f;
} int main(){
memset(f,0x3f,sizeof(f));
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]),a[i]++;
f[][a[]]=;
for(int i=,s1,s2;i<=n;i++){
f[i][]=min(f[i][],f[i-][]+calc(a[i],,));
f[i][]=min(f[i][],f[i-][]+calc(a[i],,),f[i-][]+calc(a[i],,));
f[i][]=min(f[i][],f[i-][]+calc(a[i],,),f[i-][]+calc(a[i],,),f[i-][]+calc(a[i],,));
}
int ans=min(f[n][],f[n][],f[n][]);
if(ans>=0x3f3f3f3f) puts("BRAK");
else printf("%d\n",ans);
return ;
}

最新文章

  1. BPM配置故事之案例5-必填与水印文本
  2. 使用staruml学习画类图
  3. linux实用的日志分析脚本
  4. rest api设计的一般原则
  5. pig的各种运行模式与运行方式详解
  6. vs2010 安装MVC 3.0
  7. HMM TOOL
  8. MyBatis学习总结_16_Mybatis使用的几个建议
  9. 嵌入式环境:挂载开发板根NFS文件系统失败
  10. HDU 4643 GSM 简单计算几何
  11. ModelDriven动作(转)
  12. 单片机驱动AT24C02存储芯片
  13. Java中如何使用非强制类型转换把字符串转换成int类型
  14. GLog 初始化说明
  15. Bootstrap里的文件分别代表什么意思及其引用方法
  16. 虚拟DOM与DOM diff算法
  17. unity脚本执行顺序
  18. 真机调试傻瓜图文教程(Xcode6.4)
  19. NOIP2018TG 初赛复习
  20. selenium(三)浏览器操作

热门文章

  1. 使用wget进行整站下载(转)
  2. centos7 网络不能重启问题 解决办法
  3. C语言连接MySQL(codeblocks)
  4. 小胖说事28------iOS中extern,static和const差别和使用方法
  5. AJAX核心XMLHTTPRequest对象
  6. gcc在出现错误的时候停止编译 -Wfatal-errors
  7. 简单的shell脚本编写
  8. Java Management Extensions (JMX) Flume
  9. POJ1077 Eight —— 正向BFS
  10. linux初级学习笔记五:bash特性详解!(视频序号:03_2,3)