DP(递归打印路径) UVA 662 Fast Food-白红宇

DP(递归打印路径) UVA 662 Fast Food

阅读量：5846 次

发布时间：2019-06-18

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

题意：n个饭店在一条直线上，给了它们的坐标，现在要建造m个停车场，饭店没有停车场的要到最近的停车场，问所有饭店到停车场的最短距离

分析：易得区间(i, j)的最短距离和一定是建在(i + j) / 2的饭店，预处理出(i, j)的距离和sum[i][j]，mark[i][j] 表示区间的最优停车场的位置，mid[i][j]表示(i + j) / 2。状态转移方程：dp[i][j] = max (dp[k-1][j-1] + sum[k][i])；

收获：学习递归打印路径

代码：

/************************************************* Author        :Running_Time* Created Time  :2015-8-29 16:42:33* File Name     :UVA_662.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 2e2 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int dp[N][33];int sum[N][N], d[N], mark[N][N], mid[N][N];int n, m;int idx;void print(int i, int j) { if (i < 1 || j < 1) return ; print (mark[i][j]-1, j-1); printf ("Depot %d at restaurant %d serves restaurant", ++idx, mid[mark[i][j]][i]); if (mark[i][j] == i) { printf (" %d\n", i); return ; } else printf ("s %d to %d\n", mark[i][j], i);}int main(void) { int cas = 0; while (scanf ("%d%d", &n, &m) == 2) { if (!n && !m) break; for (int i=1; i<=n; ++i) scanf ("%d", &d[i]); memset (sum, 0, sizeof (sum)); for (int i=1; i<=n; ++i) { mid[i][i]= i; for (int j=i+1; j<=n; ++j) { int mm = (i + j) >> 1; mid[i][j] = mm; for (int k=i; k<=j; ++k) { sum[i][j] += abs (d[mm] - d[k]); } } } memset (dp, INF, sizeof (dp)); memset (dp[0], 0, sizeof (dp[0])); for (int i=1; i<=n; ++i) { for (int j=1; j<=m; ++j) { for (int k=1; k<=i; ++k) { int tmp = dp[k-1][j-1] + sum[k][i]; if (dp[i][j] >= tmp) { dp[i][j] = tmp; mark[i][j] = k; } } } } printf ("Chain %d\n", ++cas); idx = 0; print (n, m); printf ("Total distance sum = %d\n\n", dp[n][m]); } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4773925.html

你可能感兴趣的文章