URAL 1029

清疚 2021-12-14 00:45 232阅读 0赞

**题目大意：**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][http_blog.csdn.net_jsun_moon]

转载于:https://www.cnblogs.com/james1207/p/3279881.html

[http_blog.csdn.net_jsun_moon]: http://blog.csdn.net/jsun_moon