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