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