這題猛然一看像是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)（同行或上面一行）。
類(lèi)比數(shù)字三角形，寫(xiě)出一個(gè)遞推式
： d[i][j]=max (d[i][j-1],d[i][j+1],d[i+1][j],d[i+1][j+1]);
無(wú)疑這是一種錯(cuò)誤的寫(xiě)法，因?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]來(lái)自同行某個(gè)數(shù)，只能來(lái)自d[i][j-1]或d[i][j+1]其中一個(gè)。
于是有了一個(gè)基本的思路：
對(duì)于每一行來(lái)說(shuō)先向右遞推，再向左遞推，遞推式為
：d[i][j]=min (d[i][j],d[i-1][j]+a[i][j])
向左推的遞推式類(lèi)似地可以寫(xiě)出。
每行左右遞推各一次即可，環(huán)的問(wèn)題根本不需要擔(dān)心。d[i][j]必來(lái)自于左推和右推時(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)，說(shuō)明左右互不影響，只是從中選擇一個(gè)即可。
循環(huán)進(jìn)入上一行之后，開(kāi)始遞推向上走的情況，和數(shù)字三角形遞推式一樣，不過(guò)邊緣需要單獨(dú)考慮，不再給出
：d[i][j]=min(d[i+1][j],d[i+1][j+1])+a[i][j]
另外說(shuō)出我在寫(xiě)程序的時(shí)候遇到的一些情況，我要開(kāi)200萬(wàn)的long數(shù)組，寫(xiě)在main()中，沒(méi)有成功，提示出錯(cuò)，我不想用壓縮存儲(chǔ)，看某人的程序把數(shù)組定義為全局，我當(dāng)時(shí)不知道為什么他要那么做，學(xué)著設(shè)為全局變量（如下），成功了~！在做noip2008第三題的時(shí)候也一樣，要開(kāi)[51][51][51][51]的數(shù)組（當(dāng)然后來(lái)知道可以降一維），開(kāi)不了，改成全局變量，又成功了~！
以下是我的代碼：
#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;
}