UVA 116 Unidirectional TSP DP-白红宇

UVA 116 Unidirectional TSP DP

阅读量：6504 次

发布时间：2019-06-24

本文共 4104 字，大约阅读时间需要 13 分钟。

　　题目链接： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=52

　　题目描述：一个整数矩阵，求第一列到最后一列的最小整数和，只能从第一列出发向右，右下，右上走，第一行的上一行是第m行，第m行的下一行是第一行，打印出字典序最小方案

　　解题思路：很简单的一个DP，状态很容易设计， dp(i, j)表示从格子a(i, j)出发到最后一列的最小开销， dp(i, j) = min( dp(i-1, j+1), dp(i, j+1), dp(i+1, j+1) )，其中有一些细节需要注意，具体在代码中实现

　　代码：这是我的错误代码，只能够过得掉样例....打印路径难道我了......怎么说也搞了一年了啊.....真的菜

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               using namespace std;int a[15][105]; //int dp[15][105]; // dp(i, j) 表示以从第一行出发a(i, j)为结尾的最短距离const int INF = 0x3fffffff;int past[15][105]; // -1 a[i][j]上个点是a[i-1][j] 0......1......stack
               
                 S;int main() { int m, n; while( ~scanf( "%d%d", &m, &n ) ) { for( int i = 1; i <= m; i++ ) { for( int j = 1; j <= n; j++ ) { scanf( "%d", &a[i][j] ); if( j == 1 ) dp[i][j] = a[i][j]; else dp[i][j] = INF; } } memset(past, 0, sizeof(past));// for( int i = 1; i <= m; i++ ) {// past[i][1] = INF;// } for( int j = 2; j <= n; j++ ) { for( int i = 1; i <= m; i++ ) { dp[i][j] = dp[i][j-1]+a[i][j]; if( i > 1 ) { if( dp[i-1][j-1]+a[i][j] <= dp[i][j] ) { dp[i][j] = dp[i-1][j-1]+a[i][j]; past[i][j] = -1; } } else { if( dp[m][j-1]+a[i][j] < dp[i][j] ) { dp[i][j] = dp[m][j-1]+a[i][j]; past[i][j] = -1; } }// if( i == 1 && j == 3 ) cout << "==" << dp[i][j] << endl; if( i < m ) {// if( i == 1 && j == 3 ) cout << "==" << dp[i+1][j-1] << " " << a[i][j] << endl; if( dp[i+1][j-1]+a[i][j] < dp[i][j] ) { dp[i][j] = dp[i+1][j-1]+a[i][j]; past[i][j] = 1; } } else { if( dp[1][j-1]+a[i][j] <= dp[i][j] ) { dp[i][j] = dp[1][j-1]+a[i][j]; past[i][j] = 1; } } } }// for( int i = 1; i <= m; i++ ) {// for( int j = 1;j <= n; j++ ) {// cout << dp[i][j] << " ";// }// cout << endl;// } int ans = INF; int index = -1; for( int i = 1; i <= m; i++ ) { if( dp[i][n] < ans ) { ans = dp[i][n]; index = i; } } S.push(index); for( int i = n; i > 1; i-- ) { if( past[index][i] == 0 ) { S.push(index); } else if( past[index][i] == -1 ) { if( index == 1 ) { S.push(index = m); } else { S.push(--index); } } else { if( index == m ) { S.push(index = 1); } else { S.push(++index); } } } while( !S.empty() ) { if( (int)S.size() == 1 ) printf( "%d", S.top() ); else { printf( "%d ", S.top() ); } S.pop(); } printf( "\n" ); printf( "%d\n", ans ); } return 0;}

View Code

　　AC 代码

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;int d[15][150]; // d[i][j] means 以a[i][j]为起点到最后一列的最短距离int a[15][150];int nextt[15][150]; // a[i][j] 下一个点是第next[i][j]行const int INF = 0x3fffffff;int main() { int m, n; while( ~scanf( "%d%d", &m, &n ) ) { for( int i = 0; i < m; i++ ) { for( int j = 0; j < n; j++ ) { scanf( "%d", &a[i][j] ); } } int ans = INF; int first = 0; for( int j = n-1; j >= 0; j-- ) { for( int i = 0; i < m; i++ ) { if( j == n-1 ) d[i][j] = a[i][j]; // 边界 else { int rows[3] = { i, i-1, i+1 }; if( i == 0 ) rows[1] = m-1; if( i == m-1 ) rows[2] = 0; sort( rows, rows+3 ); d[i][j] = INF; for( int k = 0; k < 3; k++ ) { int temp = d[rows[k]][j+1] + a[i][j]; if( temp < d[i][j] ) { d[i][j] = temp; nextt[i][j] = rows[k]; } } } } }// for( int i = 0; i < m; i++ ) {// for( int j = 0; j < n; j++ ) {// cout << d[i][j] << " ";// }// cout << endl;// } for( int i = 0; i < m; i++ ) { if( d[i][0] < ans ) { ans = d[i][0]; first = i; } } printf( "%d", first+1 ); for( int i = nextt[first][0], j = 1; j < n; i = nextt[i][j], j++ ) { printf( " %d", i+1 ); } printf( "\n" ); printf( "%d\n", ans ); } return 0;}

View Code

　　思考：本来是一道简单的DP题，自己却写了一上午，主要收获如下，在要求打印路径的时候就要注意设计的状态应该是以dp[i][j]为起点，不然会有一些BUG，比如上面的错误代码，还有一点很重要一点就是：如果用数组迭代的话，要保证在计算d[i][j] 时候，你后面的状态转移设计到的式子全部已经有值........这点非常重要，因为动态规划应该满足最优子结构，也就是说，子结构的值我应该知道，如果想要倒过来求的话，（边界值在一边，开始计算在另一边）就应该用到函数递归（记忆化搜索），其实可以说的数组迭代就是递归的一部分（函数到底后反过来求值那一段。）自己还是不熟啊，为了区域赛能拿牌！加紧练习！

转载于:https://www.cnblogs.com/FriskyPuppy/p/7272994.html

你可能感兴趣的文章

silk v3 decoder php,解码转换QQ微信的SILK v3编码音频为MP3或其他格式