首页 > 代码库 > 特种部队（codevs 1427）
特种部队（codevs 1427）
题目描述 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>#define M 1010#define INF 1000000000using namespace std;int a[M],f[M][M],n,dis[M][M],ans=INF;int main(){ memset(f,0x3f3f3f3f,sizeof(f)); scanf("%d",&n); int i,j; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) for(j=1;j<=n;j++) dis[i][j]=abs(a[i]-a[j]); f[0][0]=0; for(i=0;i<=n;i++) for(j=0;j<=n;j++) { int k=max(i,j)+1; 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=1;i<=n;i++) { ans=min(ans,f[i][n]+dis[i][n]); ans=min(ans,f[n][i]+dis[n][i]); } printf("%d",ans); return 0;}
特种部队（codevs 1427）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。