URAL 1029

题目大意：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

下来我们来证明，最后得出的必然是最优解。

左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]

呼呼，好累啊。。。不过应该是表述清楚啦、、、(*^__^*) 嘻嘻……

代码如下：

 
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
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"[] |" < inline bool updateMin(T& a, T b) { return a>b  a=b, true: false; }  
template inline bool updateMax(T& a, T b) { return adp[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[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;  
}