HDU 1227 Fast Food (DP)

题意：有n个饭店，要求建k个供应点，要求每个供应点一定要建造在某个饭店的位置上，然后饭店都到最近的供应点拿货，求出所有饭店到最近的供应点的最短距离。

思路：一开始没看出来是DP，后来想想就想通了。预处理，如果要在下标为 i 到 j 的饭店建一个供应点，那一定是在下标为（i+j）/2的位置建造的，状态转移方程：dp[i][j] = dp[i-1][k-1]+dis[k][j](i <= k <= j) ,dp[i][j]代表的是在前 j 个饭店中建了 i 个供应点的最小距离。方程代表的是在前k-1个饭店中已经建了i-1个供应点的最小距离再加上从第k个饭店到第j个饭店建一个供应点增加的距离。如果不明白可以看这里，链接

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <math.h>

 using namespace std;

 const int maxn = 0x7fffffff ;

 int a[] ,dis[][],dp[][];

 int main()

 {

     int n,k ,cas = ;

     while(~scanf("%d %d",&n,&k))

     {

         if(n ==  && k ==  ) break ;

         for(int i =  ; i <= n ; i++)

             scanf("%d",&a[i]) ;

         for(int i =  ; i <= n ; i++)

         {

             for(int j = i ; j <= n ; j++)

             {

                 dis[i][j] =  ;

                 for(int k = i ; k <= j ; k++)

                     dis[i][j] += fabs(a[k]-a[(i+j)/] );

             }

         }

         memset(dp,,sizeof(dp)) ;

         for(int i =  ; i <= n ; i++)

             dp[][i] = dis[][i] ;

         for(int i =  ; i <= k; i++)

         {

             for(int j =  ; j <= n ; j++)

             {

                 int minn = maxn ;

                 for(int k = i ; k <= j ; k++)

                 {

                     if(dp[i-][k-]+dis[k][j] < minn)

                         minn = dp[i-][k-]+dis[k][j] ;

                 }

                 dp[i][j] = minn ;

             }

         }

           printf("Chain %d\nTotal distance sum = %d\n\n",cas++,dp[k][n]);

     }

     return ;

 }

巴特西

HDU 1227 Fast Food (DP)

最新文章

热门文章