UVA116 Unidirectional TSP easy DP - c++编程基础

一道DP，题意：一张图，从第一列走到最后一列，花费最小，每次只能向右下或右上或正右方走，每一步花费为当前格子值，要求输出最小花费，并按字典序输出路线的行变换，这里的字典序要小心，因为这个图从第一行可以直接到最后一行，反之也可以，所以相当于同样的两张图上下拼接

思路：因为要输出路径，所以用DP做的时候得逆序来做，从最后一列找到第一列，状态转移方程很简单，边界也很好找:

dp[i][n]=mp[i][n] 即可

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[112][112]; int mp[112][112]; int row,col; void clear() { memset(dp,0,sizeof(dp)); memset(mp,0,sizeof(mp)); } int detal(int x) { x = x%row; if(x == 0) return row; else return x; } int main() { while(scanf("%d %d",&row,&col) == 2) { clear(); for(int i=1;i<=row;i++) { for(int j=1;j<=col;j++) { scanf("%d",&mp[i][j]); if(j == col) dp[i][j] = mp[i][j]; } } int ans = inf; int row_num = 1; for(int j=col-1;j>=1;j--) { for(int i=1;i<=row;i++) { dp[i][j] = min(dp[i][j+1],dp[detal(i+1)][j+1]) + mp[i][j]; dp[i][j] = min(dp[i][j],dp[detal(i-1)][j+1] + mp[i][j]); } } for(int i=1;i<=row;i++) { if(dp[i][1] < ans) { ans = dp[i][1]; row_num = i; } } int now_dis = ans - mp[row_num][1]; printf("%d",row_num); for(int j=2;j<=col;j++) {//注意图是上下拼接的 所以字典许输出需要处理 if(row_num == 1) { bool flag = false; for(int i=1;i<=2;i++) { if(dp[i][j] == now_dis) { printf(" %d",i); now_dis -= mp[i][j]; row_num = i; flag = true; break; } } if(!flag) {//要按字典许输出，所以最后一行放最后处理 printf(" %d",row); now_dis -= mp[row][j]; row_num = row; } } else if(row_num == row) { bool flag = false; if(now_dis == dp[1][j]) {//因为字典序输出，所以先判第一行 printf(" %d",1); now_dis -= mp[1][j]; flag = true; row_num = 1; } if(!flag) for(int i=row-1;i<=row;i++) { if(now_dis == dp[i][j]) { printf(" %d",i); now_dis -= mp[i][j]; row_num = i; break; } } } else { for(int i=row_num-1;i<=row_num+1;i++) if(now_dis == dp[i][j]) { printf(" %d",i); now_dis -= mp[i][j]; row_num = i; break; } } } puts(""); printf("%d\n",ans); } return EXIT_SUCCESS; }