UVa 116 - Unidirectional TSP

题目：求从左到右的一条路径上的加和最小。每次可以采cai取本行、上行和下行的走法。
分析：dp。数塔变形，由于要求最小序列，所以采取从右向左dp、可以保证右边的都是最小序列，每次记录后继节点，输出即可。

注意：在最上和最下两行有可能行的编号编程最大和最小的。

[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int mat[ 12 ][ 102 ]={0};
int sum[ 12 ][ 102 ]={0};
int chi[ 12 ][ 102 ]={0};

void output( int r, int c, int m )
{
    if ( c < m ) {
        printf("%d ",r);
        output( chi[r][c], c+1, m );
    }else {
        printf("%d\n",r);
    }
}

int main()
{
    int n,m;
    while ( scanf("%d%d",&n,&m) != EOF ) {
        memset( sum, 0, sizeof(sum) );
        for ( int i = 1 ; i <= n ; ++ i )
        for ( int j = 1 ; j <= m ; ++ j ) {
            scanf("%d",&mat[i][j]);
        }

        for ( int i = m ; i >= 1 ; -- i )
        for ( int j = 1 ; j <= n ; ++ j ) {
            sum[j][i] = sum[j][i+1]+mat[j][i];
            chi[j][i] = j;
            int down = j+1;
            if ( down > n ) down = 1;
            if ( sum[j][i] == sum[down][i+1]+mat[j][i] ) {
                sum[j][i] = sum[down][i+1]+mat[j][i];
                if ( chi[j][i] > down )
                    chi[j][i] = down;
            }
            if ( sum[j][i] > sum[down][i+1]+mat[j][i] ) {
                sum[j][i] = sum[down][i+1]+mat[j][i];
                chi[j][i] = down;
            }
            int up = j-1;
            if ( up < 1 ) up = n;
            if ( sum[j][i] == sum[up][i+1]+mat[j][i] ) {
                sum[j][i] = sum[up][i+1]+mat[j][i];
                if ( chi[j][i] > up )
                    chi[j][i] = up;
            }
            if ( sum[j][i] > sum[up][i+1]+mat[j][i] ) {
                sum[j][i] = sum[up][i+1]+mat[j][i];
                chi[j][i] = up;
            }
        }
        int minv = 0x7ffffff,space = 1;
        for ( int i = 1 ; i <= n ; ++ i )
            if ( minv > sum[i][1] ) {
                minv = sum[i][1];
                space = i;
            }

        output( space, 1, m );
        printf("%d\n",minv);
    }
    return 0;
}

补充：软件开发 , C++ ,