特种部队(codevs 1427)
2024-09-06 16:35:12
题目描述 Description
某特种部队接到一个任务,需要潜入一个仓库。该部队士兵分为两路,第一路士兵已经在正面牵制住了敌人,第二路士兵正在悄悄地从后方秘密潜入敌人的仓库。
当他们到达仓库时候,发现这个仓库的锁是一把很诡异的电子锁,上面是一排按钮,每个按钮上都有一个数字。10 秒钟后,总部返回了该锁的技术信息。要解开这把锁,首先要从左边的第一个按钮开始向右按动,中间可以跳过某些按钮,按动到最右边的按钮后,反向向左按动。最终,每个按钮都要按且仅按一次。每两个相邻按钮上数字之差的总和的最小值,便是解开这把锁的密码。
作为一支装备精良的特种部队,必须要在最短的时间内完成任务,解开这把锁,潜入仓库。
输入描述 Input Description
第一行是一个n(2 <= n <= 1000)表示共有n 个按钮。
第二行是n 个正整数,代表从左至右各按钮上的数字,数值均不超过2000。
输出描述 Output Description
只有一个数,为这把锁的密码。
样例输入 Sample Input
5
1 2 3 4 5
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
2 <= n <= 1000,数值不超过2000
/*
又题意的,我们可以分成两条路
f[i][j]代表一条路走到i,一条路走到j的最小值
转移方程f[i][k]=min(f[i][j]+dis[j][k])
f[k][j]=min(f[k][j]+dis[i][k])
(k=max(i,j))
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[],f[][],n,dis[][],ans=0x7fffffff;
int main()
{
cin>>n;
int i,j;
for(i=;i<=n;i++)
cin>>a[i];
for(i=;i<=n;i++)
for(j=;j<=n;j++)
dis[i][j]=abs(a[i]-a[j]);
memset(f,/,sizeof(f));
f[][]=;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
{
int k=max(i,j)+;
f[i][k]=min(f[i][k],f[i][j]+dis[j][k]);
f[k][j]=min(f[k][j],f[i][j]+dis[i][k]);
}
for(i=;i<=n;i++)
{
ans=min(ans,f[i][n]+dis[i][n]);
ans=min(ans,f[n][i]+dis[n][i]);
}
cout<<ans;
return ;
最新文章
- Thrift-java实例
- 虚拟机安装Macintosh探索
- css font-family 字体全介绍,\5b8b\4f53 宋体 随笔
- ***codeigniter 2.2 affected_rows()返回值不准确
- To follow the path
- struts2 request内幕 为什么在struts2用EL表达式可以取值
- 第一篇:NSOperation的概念
- ural1553 Caves and Tunnels
- 互相关(cross-correlation)及其在Python中的实现
- 在Centos中部署nginx
- fiddler基本功能介绍
- spring+springmvc+hibernate 整合
- 保存标注对象到txt 制作xml
- ubuntu16.04 Docker默认存储路径修改
- SAP中的ALE, IDOC
- BootStrap学习之栅格布局
- Linux之linux基础命令2
- NYOJ 石子合并(一)(区间DP)
- java -io字符流FileWrite操作演示
- oracle11g安装(win10)
热门文章
- 187 Repeated DNA Sequences 重复的DNA序列
- [转]Monkey测试简介
- 一个DBA萌新的烦恼
- Kickstart Round D 2017 : A
- (Android MVVM)使用Data Binding Library(1)
- TNS-00511: 无监听程序
- 将php中session存入redis中
- Node.js——获取文件上传进度
- jQuery addClass removeClass toggleClass方法概述
- SweetAlert如何实现点击Confirm之后自动关闭