題目大意：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; }

? ? 其中cost數組即為題目分析中的a數組了。

?

by:Jsun_moon?http://blog.csdn.net/jsun_moon

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的URAL 1029的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。