[中等] UVa OJ 116 Unidirectional TSP 动态规划

题目描述

基本思路：

首先这是一个多阶段决策问题，所以考虑采用动态规划来解。而题目最后输出路径时要求按字典序，所以从后向前进行迭代求解。

状态转移方程：d[i][j]=cost[i][j]+min{d[i-1][j+1],d[i][j+1],d[i+1][j+1]}。不过此处要注意因为允许“wrap"，所以当i-1应为(i-1+m)%m，而i+1应为(i+1)%m。

然后对于如何打印路径，可以多开一个数组next[maxm][maxn]来保存路径中当前列的下一列的行数。也可以采用从前向后找的方法。下面代码中采用了第二种方法（从前向后找）。

注意打印行数时的编码技巧，rows数组的使用。

具体代码：

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;
const int maxm=10+2;
const int maxn=100+3;
int c[maxm][maxn];
long long d[maxm][maxn];
int main()
{
   // freopen("input.txt","r",stdin);
    int m,n;
    while(cin>>m>>n)
    {
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
            {
                cin>>c[i][j];
                d[i][j]=LLONG_MAX;
            }
        for(int i=0;i<m;++i)
            d[i][n-1]=c[i][n-1];
        for(int j=n-2;j>=0;--j)
        {
            for(int i=0;i<m;++i)
            {
                d[i][j]=c[i][j]+min(min(d[(i-1+m)%m][j+1],d[i][j+1]),d[(i+1)%m][j+1]);
            }
        }
        long long ans=d[0][0];
        int lasti=0;
        for(int i=1;i<m;++i)
        {
            if(d[i][0]<ans)
            {
                ans=d[i][0];
                lasti=i;
            }
        }
        cout<<lasti+1;
        for(int j=1;j<n;++j)
        {
            int rows[3]={(lasti-1+m)%m,lasti,(lasti+1)%m};
            sort(rows,rows+3);
            for(int i=0;i<3;++i)
                if(d[rows[i]][j]+c[lasti][j-1]==d[lasti][j-1])
                {
                    cout<<" "<<rows[i]+1;
                    lasti=rows[i];
                    break;
                }
            //The code below can also print the right path, but it is a little complex and not concise.
            /*if(lasti+1>=m&&d[0][j]==d[lasti][j-1]-c[lasti][j-1])
            {
                lasti=0;
                cout<<" 1";
            }
            else if(lasti-1>=0&&d[lasti-1][j]==d[lasti][j-1]-c[lasti][j-1])
            {
                cout<<" "<<lasti;
                --lasti;
            }
            else if(d[lasti][j]==d[lasti][j-1]-c[lasti][j-1])
            {
                cout<<" "<<lasti+1;
            }
            else if(d[lasti+1][j]==d[lasti][j-1]-c[lasti][j-1])
            {
                cout<<" "<<lasti+2;
                ++lasti;
            }
            else
            {
                cout<<" "<<m;
                lasti=m-1;
            }*/
        }
        cout<<endl;
        cout<<ans<<endl;
    }
    return 0;
}