這題猛然一看像是IOI 94“數(shù)字三角形”，但仔細(xì)看上去比“數(shù)字三角形”復(fù)雜了許多。

不同之處在于：

1.       數(shù)字三角形中可以以第n行任意一個(gè)數(shù)字為起點(diǎn)，而Hill的起點(diǎn)在左下角；

2.       數(shù)字三角形中只可以不停向上走，不可以同行之間走，而此題可以；

3.       此題中可以從一行的一個(gè)端點(diǎn)直接繞到另一個(gè)端點(diǎn)（同行或上面一行）。

類比數(shù)字三角形，寫出一個(gè)遞推式

： d[i][j]=max (d[i][j-1],d[i][j+1],d[i+1][j],d[i+1][j+1]);

無疑這是一種錯(cuò)誤的寫法，因?yàn)槌霈F(xiàn)了環(huán)，對(duì)于動(dòng)態(tài)規(guī)劃有了后效性。

后效性的出現(xiàn)是因?yàn)榭梢酝兄g走，但是不會(huì)走重復(fù)的點(diǎn)是可以肯定的，于是想到后效性是可以消除的。

現(xiàn)在先考慮同行的情況。

假設(shè)某一時(shí)刻走到了 (i,j) 這一點(diǎn)，在下一步?jīng)Q策的時(shí)候，要么是(i,j-1)，要么是(i,j+1)，先不考慮加減之后越界的情況。而如果選擇了(i,j-1)這個(gè)點(diǎn)，下一步再?zèng)Q策的時(shí)候，勢(shì)必不會(huì)再重復(fù)(i,j)，而只會(huì)考慮(i,j-2)。狀態(tài)d[i][j]定義為從(n,1)到點(diǎn)(i,j)的最短距離大小，若d[i][j]來自同行某個(gè)數(shù)，只能來自d[i][j-1]或d[i][j+1]其中一個(gè)。

于是有了一個(gè)基本的思路：

對(duì)于每一行來說先向右遞推，再向左遞推，遞推式為

：d[i][j]=min (d[i][j],d[i-1][j]+a[i][j])

向左推的遞推式類似地可以寫出。

每行左右遞推各一次即可，環(huán)的問題根本不需要擔(dān)心。d[i][j]必來自于左推和右推時(shí)更優(yōu)的一條路，若將d[i][j][0]定義為表示右推的結(jié)果，d[i][j][1]表示左推的結(jié)果，則d[i][j]的最終值為min(d[i][j][0],d[i][j][1])，這樣可能更好理解一點(diǎn)，說明左右互不影響，只是從中選擇一個(gè)即可。

循環(huán)進(jìn)入上一行之后，開始遞推向上走的情況，和數(shù)字三角形遞推式一樣，不過邊緣需要單獨(dú)考慮，不再給出

：d[i][j]=min(d[i+1][j],d[i+1][j+1])+a[i][j]

另外說出我在寫程序的時(shí)候遇到的一些情況，我要開200萬的long數(shù)組，寫在main()中，沒有成功，提示出錯(cuò)，我不想用壓縮存儲(chǔ)，看某人的程序把數(shù)組定義為全局，我當(dāng)時(shí)不知道為什么他要那么做，學(xué)著設(shè)為全局變量（如下），成功了~！在做noip2008第三題的時(shí)候也一樣，要開[51][51][51][51]的數(shù)組（當(dāng)然后來知道可以降一維），開不了，改成全局變量，又成功了~！

#include<stdio.h>
#define maxint 2000000000
#define min(a,b) (a<b?a:b)
long a[1000][1000]={0};
long d[1000][1000]={0};
int main()
{
    long n,i,j,k,tmp,x1,x2;
    scanf("%ld",&n);
    for(i=0;i<n;i++)
      for(j=0;j<=i;j++)
        scanf("%ld",&a[i][j]);//------Read In
    for(i=0;i<n;i++)
      for(j=0;j<=i;j++)
        d[i][j]=maxint;
    for(i=0;i<n;i++)
      d[n-1][i]=a[n-1][i];
    for(i=1;i<n;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\n",d[0][0]);
return 0;
}