P1547逆转，然后再见
2024-09-07 14:09:19
描述
上届的高三在这个暑假终于要到各个城市奔向他们的大学生活了。奇怪的是学校这次异
常阔气，说要用三台车子去载他们上学。上届高三的师兄们异常兴奋……可惜的是临行的时
候，学校终于露出它“狰狞”的面孔：
一、油费要学生自己给
二、去第k 个城市的条件是，前k-1 个城市都要被去过
三、同时只能有一部车子在动
师兄们也只能不断地锤胸口……
但是改乘飞机已经来不及了……
他们只好利用电脑组的优势去编一个最短路径以减少自己付的油费。
（P.S．没有人喜欢走回头路……）
格式
输入格式
第一行一个数N，代表一共要去多少个城市。
下面N-1 行，对于第 i 行，有 n-i 个数，表示第 i 个城市分别和第i+1, i+2, i+3, ……, N 的距离
输出格式
一行，最短的路程
限制
每个数据 1s
提示
N<=100
思路：dp
dp[i][j][k]表示第一辆车在第i个城市，第二辆车在第j个城市，第三辆车在第k个城市的最小路径；
初始化:f[1][1][1]=0,其余为Max
now表示当前到达的最远的城市(即now=max(i,j,k))
f[now+1][j][k]=min(f[now+1][j][k],f[i][j][k]+a[i][now+1])
f[i][now+1][k]=min(f[i][now+1][k],f[i][j][k]+a[j][now+1])
f[i][j][now+1]=min(f[i][j][now+1],f[i][j][k]+a[k][now+1])
在所有的now=n时，记录最小值。
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<stdlib.h>
5 #include<string.h>
6 #include<math.h>
7 #include<queue>
8 using namespace std;
9 typedef long long LL;
10 int dp[105][105][105];
11 int nn[200][200];
12 const int N=1e9;
13 int main(void)
14 {
15 int i,j,k;
16 while(scanf("%d",&k)!=EOF)
17 {
18 int x,y;
19 for(i=1; i<k; i++)
20 {
21 for(j=i+1;j<=k;j++)
22 {
23 scanf("%d",&nn[i][j]);
24 }
25 }
26 for(i=0; i<105; i++)
27 {
28 for(j=0; j<105; j++)
29 {
30 for(x=0; x<105; x++)
31 {
32 dp[i][j][x]=N;
33 }
34 }
35 }
36 int ans=1e9;
37 dp[1][1][1]=0;
38 for(i=1; i<k; i++)
39 {
40 for(j=1; j<k; j++)
41 {
42 for(x=1; x<k; x++)
43 {
44 int xx=max(i,j);
45 xx=max(x,xx);
46 dp[xx+1][j][x]=min(dp[xx+1][j][x],dp[i][j][x]+nn[i][xx+1]);
47 dp[i][xx+1][x]=min(dp[i][xx+1][x],dp[i][j][x]+nn[j][xx+1]);
48 dp[i][j][xx+1]=min(dp[i][j][xx+1],dp[i][j][x]+nn[x][xx+1]);
49 if(xx+1==k)
50 {ans=min(dp[xx+1][j][x],ans);
51 ans=min(dp[i][j][xx+1],ans);
52 ans=min(ans,dp[i][xx+1][x]);
53 }
54 }
55 }
56 }
57 printf("%d\n",ans);
58 }
59 return 0;
60 }
最新文章
- 玩转GIT
- springmvc和http404错误
- awk多模式匹配
- linux系统中errno与error对照表
- MVP 个人理解2
- Laravel Eloquent 判断取出的结果集是否为空
- IE11兼容IE9问题
- Spring与Hibernate集成中的Session问题
- httpd2.4常用配置
- [国嵌笔记][008-009][远程登录Linux]
- Redis源码学习：字符串
- Eclipse常用设置及快捷键
- 几个NAND/NOR门可以表示一个XOR门？
- SQL server 2012 数据库日志缓存过大
- socket 聊天室
- solus 系统 - 更新软件源
- Boostrap导航栏跳转到其他页面或外部链接
- 微信小程序之 ----API接口
- ORA-10922 Temporary tablespace group is empty错误
- java Apache common-io 讲解