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; 
}