首页 > vijos 1006 晴天小猪历险记之Hill——数字三角形的终极变化

vijos 1006 晴天小猪历险记之Hill——数字三角形的终极变化

题目链接:https://vijos.org/p/1006

数字三角形原题看这里:http://www.cnblogs.com/huashanqingzhu/p/7326837.html

背景

在很久很久以前,有一个动物村庄,那里是猪的乐园(^_^),村民们勤劳、勇敢、善良、团结……

不过有一天,最小的小小猪生病了,而这种病是极其罕见的,因此大家都没有储存这种药物。所以晴天小猪自告奋勇,要去采取这种药草。于是,晴天小猪的传奇故事便由此展开……

描述

这一天,他来到了一座深山的山脚下,因为只有这座深山中的一位隐者才知道这种药草的所在。但是上山的路错综复杂,由于小小猪的病情,晴天小猪想找一条需时最少的路到达山顶,但现在它一头雾水,所以向你求助。

山用一个三角形表示,从山顶依次向下有1段、2段、3段等山路,每一段用一个数字T(1<=T<=100)表示,代表晴天小猪在这一段山路上需要爬的时间,每一次它都可以朝左、右、左上、右上四个方向走。山是环形的。(**注意**:在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段)。

晴天小猪从山的左下角出发,目的地为山顶,即隐者的小屋。

★★★**本题为vijos早年陈题,描述晦涩,现重新描述题面如下**★★★

有一个数字三角形,共nn行,依次编号为第一行,第二行至第nn行。其中第ii行有ii个数字,位置依次记为(i,1),(i,2)(i,1),(i,2)到(i,i)(i,i)。

现在从第nn层的第一个位置出发(即(n,1)),每一步移到相邻的,且行编号小于或等于当前行编号的一个位置中,直到(1,1)结束,在不重复经过任何位置的情形下,路过的所有位置(包括端点)的对应数字之和最小。

下面详细定义相邻关系。

同一层内连续的两个位置相邻,特别的有每一层第一个位置与最后一个位置相邻。

对于位置(i,j),它与(i-1,j-1)以及(i-1,j)相邻,特别的(i,1)(i-1,i-1)相邻,且(i,i)(i-1,1)相邻。

格式

输入格式

第一行有一个数n(2<=n<=1000),表示山的高度。

从第二行至第n+1行,第i+1行有i个数,每个数表示晴天小猪在这一段山路上需要爬的时间。

输出格式

一个数,即晴天小猪所需要的最短时间。

样例1

样例输入1

5
1
2 3
4 5 6
10 1 7 8
1 1 4 5 6

样例输出1

10

限制

各个测试点1s

提示

在山的两侧的走法略有特殊,请自己模拟一下,开始我自己都弄错了……

来源

Sunnypig

算法分析:

参考:

http://blog.csdn.net/Little_Flower_0/article/details/47945611

https://vijos.org/p/1006/solution

http://www.cnblogs.com/candy99/p/5981533.html

 算法一:

建立图,然后求最短路径。(来源)

(从上往下建)

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 using namespace std;
 8 typedef long long ll;
 9 const int N=1005*1005/2,INF=1e9+5;
10 inline int read(){
11     char c=getchar();int x=0,f=1;
12     while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();}
13     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
14     return x*f;
15 }
16 int n,t[N],u,v,w;
17 inline int id(int i,int j){
18     return i*(i-1)/2+j;
19 }
20 struct edge{
21     int v,ne;
22 }e[N<<1];
23 int cnt=0,h[N];
24 inline void add(int u,int v){
25     cnt++;
26     e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
27 }
28 inline void ins(int u,int v){
29     add(u,v);add(v,u);
30 }
31 int d[N],inq[N];
32 queue<int> q;
33 void spfa(int s){
34     int m=id(n,n);
35     for(int i=1;i<=m;i++) d[i]=INF;
36     d[s]=0;
37     q.push(s);
38     while(!q.empty()){
39         int u=q.front();q.pop();
40         inq[u]=0;
41         for(int i=h[u];i;i=e[i].ne){
42             int v=e[i].v,w=t[u];
43             if(d[v]>d[u]+w){
44                 d[v]=d[u]+w;
45                 if(!inq[v]){inq[v]=1;q.push(v);}
46             }
47         }
48     }
49 }
50 int main(){
51     n=read();
52     for(int i=1;i<=n;i++){
53         if(i!=1) ins(id(i,1),id(i,i));
54         if(i1){
55             add(id(i,i),id(i+1,1));
56             add(id(i,1),id(i+1,i+1));
57         }
58         for(int j=1;j<=i;j++){
59             t[id(i,j)]=read();
60             if(j1));
61             if(i1,j)),add(id(i,j),id(i+1,j+1));            
62         }
63     }
64     spfa(id(1,1));
65     printf("%d",d[id(n,1)]+t[id(n,1)]);
66 }
View Code

或者参考下面的这一段代码:

最短路很容易~

但是建图有点麻烦~~

因为考虑到如果从一个点往上连边的话

会有点小麻烦(可能不存在~)

那么我们可以从每一个点开始

每一个可以走到它的点向他连边

即向下找往上连

如果是在一行的首位置或者末位置就有5种被走上来的方法

否则四种走法

这个需要很小心注意一个地方写错了就gg(调了半小时)

好坑的地方就是这里的右上方=上方....

害怕~

然后用个等差数列求和公式求出对应的顶标就好啦~

 代码来源:https://vijos.org/p/1006/solution

  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 using namespace std;
  7 
  8 const int MAXn=1005;
  9 const int MAXN=500501;
 10 const int MAXM=2500001;
 11 const int INF=(1<<30)-1;
 12 struct Edge
 13 {
 14     int to,w,next;
 15 }e[MAXM];
 16 int fisrt[MAXN];//Edges
 17 queue<int> q;
 18 int d[MAXN],in[MAXN];//SPFA
 19 int w[MAXn][MAXn];
 20 int l,n,tot;
 21 
 22 inline void Add_Edge(int x,int y,int w)
 23 {
 24     e[++tot].to=y;  e[tot].w=w;
 25     e[tot].next=fisrt[x];   fisrt[x]=tot;
 26 }
 27 
 28 inline int getn(int x,int y)
 29 {
 30     return x*(x-1)/2+y;
 31 }
 32 
 33 void init()
 34 {
 35     memset(fisrt,-1,sizeof(fisrt));
 36     scanf("%d",&l); n=getn(l,l);
 37     for(int i=1;i<=l;i++)
 38         for(int j=1;j<=i;j++)
 39             scanf("%d",&w[i][j]);
 40 }
 41 
 42 void getmap()//建图从上向下建更方便
 43 {
 44     Add_Edge(2,1,w[2][1]);
 45     Add_Edge(3,1,w[2][2]);
 46     for(int i=2;i<=l;i++)
 47         for(int j=1;j<=i;j++)
 48         {
 49             int u=getn(i,j);
 50             if(j==1)
 51             {
 52                 Add_Edge(getn(i,i),u,w[i][i]);
 53                 Add_Edge(getn(i,j+1),u,w[i][j+1]);
 54                 if(i!=l)
 55                     Add_Edge(getn(i+1,i+1),u,w[i+1][i+1]),
 56                     Add_Edge(getn(i+1,j),u,w[i+1][j]),
 57                     Add_Edge(getn(i+1,j+1),u,w[i+1][j+1]);
 58             }
 59             else    if(j==i)
 60             {
 61                 Add_Edge(getn(i,j-1),u,w[i][j-1]);
 62                 Add_Edge(getn(i,1),u,w[i][1]);
 63                 if(i!=l)
 64                     Add_Edge(getn(i+1,j),u,w[i+1][j]),
 65                     Add_Edge(getn(i+1,1),u,w[i+1][1]),
 66                     Add_Edge(getn(i+1,j+1),u,w[i+1][j+1]);
 67             }
 68             else
 69             {
 70                 Add_Edge(getn(i,j-1),u,w[i][j-1]);
 71                 Add_Edge(getn(i,j+1),u,w[i][j+1]);
 72                 if(i!=l)
 73                     Add_Edge(getn(i+1,j),u,w[i+1][j]),
 74                     Add_Edge(getn(i+1,j+1),u,w[i+1][j+1]);
 75             }
 76         }
 77 }
 78 
 79 void SPFA(int s)
 80 {
 81     memset(d,0x37,sizeof(d));
 82     q.push(s);  d[s]=0;  in[s]=1;
 83     while(!q.empty())
 84     {
 85         int u=q.front();    q.pop();    in[u]=0;
 86         for(int i=fisrt[u];i!=-1;i=e[i].next)
 87         {
 88             int& v=e[i].to; int& w=e[i].w;
 89             if(d[v]>d[u]+w)
 90             {
 91                 d[v]=d[u]+w;
 92                 if(!in[v])
 93                 {
 94                     q.push(v);
 95                     in[v]=1;
 96                 }
 97             }
 98         }
 99     }
100     cout<1]+w[1][1]<<endl;
101 }
102 
103 int main()
104 {
105     init();
106     getmap();
107     SPFA(getn(l,1));
108 }
View Code

 

 算法二:动态规划

 说实话,上面那一长段的关于动规算法的描述,我是真没看懂,直接看代码还大概清楚一点。

下面代码中,f[i][j]表示从(i,j)这个位置到达顶部(1,1)这个位置的最短距离。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 using namespace std;
 6 
 7 const int maxn=1005;
 8 int a[maxn][maxn];
 9 int f[maxn][maxn];
10 int n;
11 
12 int main()
13 {
14     cin>>n;
15     for(int i=1;i<=n;i++)
16         for(int j=1;j<=i;j++)
17         cin>>a[i][j];
18     f[1][1]=a[1][1];//终点处就直接是该点时间
19     for(int i=2;i<=n;i++)//一层一层往上推
20     {
21         for(int j=2;j//先求出从上一层推出来的最小值
22             f[i][j]=min(f[i-1][j],f[i-1][j-1])+a[i][j];
23         f[i][1]=min(f[i-1][1],f[i-1][i-1])+a[i][1];//特殊边界点处理
24         f[i][i]=min(f[i-1][i-1],f[i-1][1])+a[i][i];//特殊边界点处理
25         //同一层更新最优解
26         for(int k=i-1;k>0;k--)//从右往左推 从右往左走的情况更新
27             f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
28         f[i][i]=min(f[i][i],f[i][1]+a[i][i]);
29 
30         for(int l=2;l<=i;l++)//从左往右推 从左往右走的情况更新
31             f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
32             f[i][1]=min(f[i][1],f[i][i]+a[i][1]);
33         //我也没太明白为何需要下面这两个for,把上面的事情再做一遍。我把下面这两个for屏蔽以后确实是可以AC的。假如真有原因,估计要读上面那一长段文字了
34         for(int k=i-1;k>0;k--)//再推一遍从右往左推 从右往左走的情况更新
35             f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
36             f[i][i]=min(f[i][i],f[i][1]+a[i][i]);
37 
38         for(int l=2;l<=i;l++)//再推一遍从左往右推 从左往右走的情况更新
39             f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
40                 f[i][1]=min(f[i][1],f[i][i]+a[i][1]);
41     }
42     cout<1]<<endl;
43 }

上面这一段代码来自vijos讨论版块:https://vijos.org/p/1006/solution

下面是另一个动规代码,可以与上面这一段互相对照理解。代码来源:http://blog.csdn.net/Little_Flower_0/article/details/47945611

下面这段代码中,d[i][j]表示从(i,j)这个位置到达底层的最短距离。

 1 #include
 2 #define maxint 2000000000
 3 #define min(a,b) (a 4 long a[1000][1000]={ 0};
 5 long d[1000][1000]={ 0};
 6 int main()
 7 {
 8     long n,i,j;
 9     scanf("%ld",&n);
10     for(i=0;i)
11       for(j=0;j<=i;j++)
12         scanf("%ld",&a[i][j]);
13 
14     for(i=0;i)
15       for(j=0;j<=i;j++)
16         d[i][j]=maxint;
17 
18     for(i=0;i//对最后一行的处理 
19       d[n-1][i]=a[n-1][i];
20     for(i=1;i)
21       d[n-1][i]=d[n-1][i-1]+a[n-1][i];                          //因为最后一行右边的点只能从左边的推来,所以有了这个预处理 
22     for(i=n-1;i>=0;i--)                              
23       d[n-1][i]=min(d[n-1][i],d[n-1][(i+1)%n]+a[n-1][i]);       //往左走的话,肯定要先从左边翻过去再向左走 
24 
25     for(i=n-2;i>=0;i--)
26     {
27        d[i][0]=min(d[i+1][0],d[i+1][1]);                        //对左边界的处理 
28        d[i][0]=min(d[i][0],d[i+1][i+1]);
29        d[i][0]+=a[i][0];
30 
31        d[i][i]=min(d[i+1][0],d[i+1][i]);                        //对右边界的处理 
32        d[i][i]=min(d[i][i],d[i+1][i+1]);
33        d[i][i]+=a[i][i];
34 
35        for(j=1;j<=i-1;j++)                                      //对中间位置的处理,这时候下面的一行已经处理完了 
36          d[i][j]=min(d[i+1][j],d[i+1][j+1])+a[i][j];
37 
38        d[i][0]=min(d[i][0],d[i][i]+a[i][0]);                    //左推与右推 
39        for(j=1;j<=i;j++)
40          d[i][j]=min(d[i][j],d[i][j-1]+a[i][j]);
41        for(j=i;j>=0;j--)
42          d[i][j]=min(d[i][j],d[i][(j+1)%(i+1)]+a[i][j]);
43 
44     }
45     printf("%ld
",d[0][0]);
46     return 0;
47 }

 

转载于:https://www.cnblogs.com/huashanqingzhu/p/7345648.html

更多相关:

  •         Apache POI是一个开源的利用Java读写Excel,WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码:package com.xing.studyTest.poi;import java.io.FileInputSt...

  • 要取得[a,b)的随机整数,使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数,使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数,使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n;其中的a是起始值,n是整数的范围。 要取得a到b之间的...

  • 利用本征图像分解(Intrinsic Image Decomposition)算法,将图像分解为shading(illumination) image 和 reflectance(albedo) image,计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 题目:面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制: 1 <= 数组长度 <= 50000 解题: cl...

  • 题目:二叉搜索树的后序遍历序列 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树:      5     /    2   6   /  1   3示例 1: 输入: [1,6,3,2,5] 输出...

  • 用python编写乘法口诀表的方法 发布时间:2020-08-25 11:46:35 来源:亿速云 阅读:60 作者:小新 用python编写乘法口诀表的方法?这个问题可能是我们日常学习或工作经常见到的。希望通过这个问题能让你收获颇深。下面是小编给大家带来的参考内容,让我们一起来看看吧! 第一种:使用for遍历循环嵌套for x in...

  • //很长一段时间我都只使用以下方式做数组循环,具体原因看数据 var aa = for (var i = 0, l = aa.length; i < l; i++) { var a = aa[i];} 数据采集图片来源于网友 很明显,for循环第二种方式完胜!!! 至于for in、forEach什么的,不知道甩他们多少...

  • 目录 1. Scene Graph Generation with External Knowledge and Image Reconstruction 2. Knowledge Acquisition for Visual Question Answering via Iterative Querying Author...

  • 基础题1: 输入一个正整数 n (1≤n≤10)和n 阶方阵a的元素,如果方阵a中的所有元素都沿主对角线对称,输出“Yes”, 否则,输出“No”。主对角线为从矩阵的左上角至右下角的连线,方阵a中的所有元素都沿主对角线对称指对所有i, k,a[i][k]和a[k][i]相等。输入输出示例如下: 输入: 3 1 2 3 4 5 6 7...

  • 程序流程控制 分支 顺序 循环 if switch&case 1 2 3 调整 break 1.6 前 switch(byte、short、char、int) 1.7 可放String 循环 while(次数不确定) do while for(确定次数) break(跳出本层循环) continue(跳出本次循环)     *   2...