題目大意：M層N列的矩陣（各元素均為正整數），找出一個路徑從第一層到達第M層，使得路徑上的所有數的和是所有可達路徑中最小的，每次上到下一層以後就不能再上去，依次輸出路徑上的各點在所在層的列數。
Time Limit:1000MS Memory Limit:16384KB 64bit IO Format:%I64d & %I64u
數據規模：1<=M<=100,1<=N<=500，路徑上的數的總和不會超過10^9。
理論基礎：無。
題目分析：用dp[i][j]表示到達第i層第j列元素的最小路徑的值，用pre[i][j]存儲dp[i][j]狀態的上一個結點相對於j的位置，用於最後輸出答案，用a[i][j]存儲數據。
初始化dp[i][j]為INF,對dp[1][j]賦值為a[j]，理由很簡單不用多說。
下來我們探尋dp方法。左dp一遍，右dp一遍即可。
左dp時，狀態轉移方程為：dp[i][j]=min(dp[i][j-1],dp[i-1][j])+a[i][j]。
右dp時，狀態轉移方程為：dp[i][j]=min(dp[i][j],dp[i][j+1]+a[i][j])（1<=j<n）
下來我們來證明，最後得出的必然是最優解。
左dp後得到的不一定全部都是最有解，但是dp[i][n]必然是最優解，因為第i層的上一個節點只能是dp[i-1][n],與dp[i][j-1]。分情況來討論:
假設是dp[i-1][n]的話，那麼左dp時，將它與大於dp[i][j-1]最有解時的值相比結果不會改變，所以得到的必然是最優解。
假設是dp[i][j-1]的話，那麼我們可以得出，dp[i][j-1]必然是真實最優解(遞歸證明)，因為dp[i][j-1]的上一個節點只能是dp[i][j-2]或者dp[i-1][j-1],dp[i][j-2]時同情況1，dp[i][j-2]時遞歸，最終得到dp[i][1]此時，因為dp[i][1]的上一個結點只能是dp[i-1][1]，由情況1可得dp[i][1]必然是最優解，倒推回來，得出dp[i][j-1]是真實最優解，那麼dp[i][j-1]+a[i][j]也必然是最優解，即dp[i][n]是最優解得證。
如此一來，我們在右dp時，將dp[i][j]與dp[i][j+1]+a[i][j]相比時得到的也必然是最優解。
證明過程如下：
假設，dp[i][j+1]+a[i][j]>=dp[i][j]那麼說明dp[i][j]的最優解只能來自dp[i][j-1]與dp[i-1][j]由上面證明可以得出，dp[i][j]即為最優解。
假設，dp[i][j+1]+a[i][j]<dp[i][j],那麼dp[i][j]=dp[i][j+1]+a[i][j]即為最優解，因為dp[i][j+1]是真實最優解。所以右dp後所有狀態均獲得最優解，得證。
呼呼，好累啊。。。不過應該是表述清楚啦、、、(*^__^*) 嘻嘻……
代碼如下：
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<ctime>
#include<vector>
using namespace std;
typedef double db;
#define DBG 0
#define maa (1<<31)
#define mii ((1<<31)-1)
#define ast(b) if(DBG && !(b)) { printf("%d!!|\n", __LINE__); while(1) getchar(); } //調試
#define dout DBG && cout << __LINE__ << ">>| "
#define pr(x) #x"=" << (x) << " | "
#define mk(x) DBG && cout << __LINE__ << "**| "#x << endl
#define pra(arr, a, b) if(DBG) {\
dout<<#arr"[] |" <<endl; \
for(int i=a,i_b=b;i<=i_b;i++) cout<<"["<<i<<"]="<<arr[i]<<" |"<<((i-(a)+1)%8?" ":"\n"); \
if((b-a+1)%8) puts("");\
}
template<class T> inline bool updateMin(T& a, T b) { return a>b? a=b, true: false; }
template<class T> inline bool updateMax(T& a, T b) { return a<b? a=b, true: false; }
typedef long long LL;
typedef long unsigned int LU;
typedef long long unsigned int LLU;
#define M 100
#define N 500
int dp[M+1][N+1],cost[M+1][N+1];
char pre[M+1][N+1];
short ans[M*N/2+M/2+1];
int m,n,cnt;
void init()
{
cnt=0;
memset(dp,64,sizeof dp);
memset(pre,0,sizeof pre);
for(int i=1;i<=n;i++)dp[1][i]=cost[1][i];
}
void solve(int m,int n)
{
for(int i=2;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(dp[i][j-1]>dp[i-1][j])
{
dp[i][j]=dp[i-1][j]+cost[i][j];
pre[i][j]='d';
}
else
{
dp[i][j]=dp[i][j-1]+cost[i][j];
pre[i][j]='l';
}
}
for(int j=n-1;j>=1;j--)
{
if(dp[i][j+1]+cost[i][j]<dp[i][j])
{
dp[i][j]=dp[i][j+1]+cost[i][j];
pre[i][j]='r';
}
}
}
int a=m,b=1;
for(int i=2;i<=n;i++)
{
if(dp[a][b]>dp[m][i])b=i;
}
ans[cnt++]=b;
while(a!=1)
{
if(pre[a][b]=='d')
{
ans[cnt++]=b;
a--;
}
else if(pre[a][b]=='l')
{
ans[cnt++]=b-1;
b--;
}
else if(pre[a][b]=='r')
{
ans[cnt++]=b+1;
b++;
}
}
while(cnt--)printf("%hd%c",ans[cnt],cnt==0?'\n':' ');
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",*(cost+i)+j);
}
}
init();
solve(m,n);
}
return 0;
}
