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

 算法一：

建立图，然后求最短路径。（来源）

（从上往下建）

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N=1005*1005/2,INF=1e9+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){ if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n,t[N],u,v,w;
inline int id(int i,int j){
    return i*(i-1)/2+j;
}
struct edge{
    int v,ne;
}e[N<<1];
int cnt=0,h[N];
inline void add(int u,int v){
    cnt++;
    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
}
inline void ins(int u,int v){
    add(u,v);add(v,u);
}
int d[N],inq[N];
queue<int> q;
void spfa(int s){
    int m=id(n,n);
    for(int i=1;i<=m;i++) d[i]=INF;
    d[s]=0;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        inq[u]=0;
        for(int i=h[u];i;i=e[i].ne){
            int v=e[i].v,w=t[u];
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                if(!inq[v]){inq[v]=1;q.push(v);}
            }
        }
    }
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        if(i!=1) ins(id(i,1),id(i,i));
        if(i1){
            add(id(i,i),id(i+1,1));
            add(id(i,1),id(i+1,i+1));
        }
        for(int j=1;j<=i;j++){
            t[id(i,j)]=read();
            if(j1));
            if(i1,j)),add(id(i,j),id(i+1,j+1));            
        }
    }
    spfa(id(1,1));
    printf("%d",d[id(n,1)]+t[id(n,1)]);
}

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

最短路很容易~

但是建图有点麻烦~~

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

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

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

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

即向下找往上连

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

否则四种走法

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

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

害怕~

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

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

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAXn=1005;
const int MAXN=500501;
const int MAXM=2500001;
const int INF=(1<<30)-1;
struct Edge
{
    int to,w,next;
}e[MAXM];
int fisrt[MAXN];//Edges
queue<int> q;
int d[MAXN],in[MAXN];//SPFA
int w[MAXn][MAXn];
int l,n,tot;

inline void Add_Edge(int x,int y,int w)
{
    e[++tot].to=y;  e[tot].w=w;
    e[tot].next=fisrt[x];   fisrt[x]=tot;
}

inline int getn(int x,int y)
{
    return x*(x-1)/2+y;
}

void init()
{
    memset(fisrt,-1,sizeof(fisrt));
    scanf("%d",&l); n=getn(l,l);
    for(int i=1;i<=l;i++)
        for(int j=1;j<=i;j++)
            scanf("%d",&w[i][j]);
}

void getmap()//建图从上向下建更方便
{
    Add_Edge(2,1,w[2][1]);
    Add_Edge(3,1,w[2][2]);
    for(int i=2;i<=l;i++)
        for(int j=1;j<=i;j++)
        {
            int u=getn(i,j);
            if(j==1)
            {
                Add_Edge(getn(i,i),u,w[i][i]);
                Add_Edge(getn(i,j+1),u,w[i][j+1]);
                if(i!=l)
                    Add_Edge(getn(i+1,i+1),u,w[i+1][i+1]),
                    Add_Edge(getn(i+1,j),u,w[i+1][j]),
                    Add_Edge(getn(i+1,j+1),u,w[i+1][j+1]);
            }
            else    if(j==i)
            {
                Add_Edge(getn(i,j-1),u,w[i][j-1]);
                Add_Edge(getn(i,1),u,w[i][1]);
                if(i!=l)
                    Add_Edge(getn(i+1,j),u,w[i+1][j]),
                    Add_Edge(getn(i+1,1),u,w[i+1][1]),
                    Add_Edge(getn(i+1,j+1),u,w[i+1][j+1]);
            }
            else
            {
                Add_Edge(getn(i,j-1),u,w[i][j-1]);
                Add_Edge(getn(i,j+1),u,w[i][j+1]);
                if(i!=l)
                    Add_Edge(getn(i+1,j),u,w[i+1][j]),
                    Add_Edge(getn(i+1,j+1),u,w[i+1][j+1]);
            }
        }
}

void SPFA(int s)
{
    memset(d,0x37,sizeof(d));
    q.push(s);  d[s]=0;  in[s]=1;
    while(!q.empty())
    {
        int u=q.front();    q.pop();    in[u]=0;
        for(int i=fisrt[u];i!=-1;i=e[i].next)
        {
            int& v=e[i].to; int& w=e[i].w;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                if(!in[v])
                {
                    q.push(v);
                    in[v]=1;
                }
            }
        }
    }
    cout<1]+w[1][1]<<endl;
}

int main()
{
    init();
    getmap();
    SPFA(getn(l,1));
}

 

 算法二：动态规划

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

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

#include 
#include 
#include 
#include 
using namespace std;

const int maxn=1005;
int a[maxn][maxn];
int f[maxn][maxn];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
        cin>>a[i][j];
    f[1][1]=a[1][1];//终点处就直接是该点时间
    for(int i=2;i<=n;i++)//一层一层往上推
    {
        for(int j=2;j//先求出从上一层推出来的最小值
            f[i][j]=min(f[i-1][j],f[i-1][j-1])+a[i][j];
        f[i][1]=min(f[i-1][1],f[i-1][i-1])+a[i][1];//特殊边界点处理
        f[i][i]=min(f[i-1][i-1],f[i-1][1])+a[i][i];//特殊边界点处理
        //同一层更新最优解
        for(int k=i-1;k>0;k--)//从右往左推 从右往左走的情况更新
            f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
        f[i][i]=min(f[i][i],f[i][1]+a[i][i]);

        for(int l=2;l<=i;l++)//从左往右推 从左往右走的情况更新
            f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
            f[i][1]=min(f[i][1],f[i][i]+a[i][1]);
        //我也没太明白为何需要下面这两个for，把上面的事情再做一遍。我把下面这两个for屏蔽以后确实是可以AC的。假如真有原因，估计要读上面那一长段文字了
        for(int k=i-1;k>0;k--)//再推一遍从右往左推 从右往左走的情况更新
            f[i][k]=min(f[i][k],f[i][k+1]+a[i][k]);
            f[i][i]=min(f[i][i],f[i][1]+a[i][i]);

        for(int l=2;l<=i;l++)//再推一遍从左往右推 从左往右走的情况更新
            f[i][l]=min(f[i][l],f[i][l-1]+a[i][l]);
                f[i][1]=min(f[i][1],f[i][i]+a[i][1]);
    }
    cout<1]<<endl;
}

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

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

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

#include
#define maxint 2000000000
#define min(a,b) (a 4 long a[1000][1000]={ 0};
long d[1000][1000]={ 0};
int main()
{
    long n,i,j;
    scanf("%ld",&n);
    for(i=0;i)
      for(j=0;j<=i;j++)
        scanf("%ld",&a[i][j]);

    for(i=0;i)
      for(j=0;j<=i;j++)
        d[i][j]=maxint;

    for(i=0;i//对最后一行的处理 
      d[n-1][i]=a[n-1][i];
    for(i=1;i)
      d[n-1][i]=d[n-1][i-1]+a[n-1][i];                          //因为最后一行右边的点只能从左边的推来，所以有了这个预处理 
    for(i=n-1;i>=0;i--)                              
      d[n-1][i]=min(d[n-1][i],d[n-1][(i+1)%n]+a[n-1][i]);       //往左走的话，肯定要先从左边翻过去再向左走 

    for(i=n-2;i>=0;i--)
    {
       d[i][0]=min(d[i+1][0],d[i+1][1]);                        //对左边界的处理 
       d[i][0]=min(d[i][0],d[i+1][i+1]);
       d[i][0]+=a[i][0];

       d[i][i]=min(d[i+1][0],d[i+1][i]);                        //对右边界的处理 
       d[i][i]=min(d[i][i],d[i+1][i+1]);
       d[i][i]+=a[i][i];

       for(j=1;j<=i-1;j++)                                      //对中间位置的处理，这时候下面的一行已经处理完了 
         d[i][j]=min(d[i+1][j],d[i+1][j+1])+a[i][j];

       d[i][0]=min(d[i][0],d[i][i]+a[i][0]);                    //左推与右推 
       for(j=1;j<=i;j++)
         d[i][j]=min(d[i][j],d[i][j-1]+a[i][j]);
       for(j=i;j>=0;j--)
         d[i][j]=min(d[i][j],d[i][(j+1)%(i+1)]+a[i][j]);

    }
    printf("%ld
",d[0][0]);
    return 0;
}