2014上海邀请赛 C Dp + 记录路径-白红宇

2014上海邀请赛 C Dp + 记录路径

阅读量：6005 次

发布时间：2019-06-20

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

　　题目链接：https://vjudge.net/contest/160930#problem/C

　　题目描述：给一个m * n 的图，要求找一条从上到下的线使得权值和最小，先只能向下左下，下，右下转移，如果有多条，输出最靠右的那条。

　　题目思路：很明显的dp, dp(i, j)表示，前i行经过a[i][j]的最小的权值。

　　　　　　转移方程： dp(i,j) = min(dp(i-1,j-1), dp(i-1,j), dp(i-1,j+1)) + a[i][j];

　　　　　　由于要记录路径，创建path数组，在更新找到I-1行最小值的时候记录是从哪里来的。

　　题目代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #define INF 0x3fffffffusing namespace std;int dp[105][105];int a[105][105];int path[105][105];stack
               
                 s;int main() { int t; int cases = 0; scanf( "%d", &t );// cout << "Hello, World!" << endl; while( t-- ) { memset( dp, 0, sizeof( dp ) ); memset( a, 0, sizeof( a ) ); memset( path, -1, sizeof( path ) ); while( s.size() ) s.pop(); int m, n; scanf( "%d%d", &m, &n ); for( int i = 0; i < m; i++ ) { for( int j = 0; j < n; j++ ) { scanf( "%d", &a[i][j] ); if( i == 0 ) { dp[0][j] = a[0][j]; } } } for( int i = 1; i < m; i++ ) { for( int j = 0; j < n; j++ ) { int min_value = dp[i-1][j]; if( j > 0 ) { if( dp[i-1][j] <= dp[i-1][j-1] ) { path[i][j] = 1; min_value = dp[i-1][j]; } else { path[i][j] = 0; min_value = dp[i-1][j-1]; } } if( j < n-1 ) { if( dp[i-1][j+1] <= min_value ) { path[i][j] = 2; min_value = dp[i-1][j+1]; } } dp[i][j] = min_value + a[i][j]; } } int ans = INF; int index = -1; for( int k = 0; k < n; k++ ) { if( ans >= dp[m-1][k] ) { ans = dp[m-1][k]; index = k; } }// for( int i = 0; i < m; i++ ) {// for( int j = 0; j < n; j++ ) {// cout << path[i][j] << " ";// }// cout << endl;// }// cout << ans << endl; s.push( index ); int temp = index; for( int i = m-1; i >= 1; i-- ) { if( path[i][temp] == 0 ) temp--; else if( path[i][temp] == 2 ) temp++; s.push( temp ); } cout << "Case " << ++cases << endl; while( !s.empty() ) { if( s.size() > 1 ) cout << s.top()+1 << " "; else cout << s.top()+1; s.pop(); } cout << endl; } return 0;}