首页 > 代码库 > hdu 1227 Fast Food

hdu 1227 Fast Food

2024-07-14 03:35:54   223人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1227

在n个商店中建m个仓库，使各个商店到仓库的路程之和最小，商店到哪个仓库是有选择的，求路程之和最小。

dp[i][j]为建i个仓库前j个商店。

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 1000 5 using namespace std; 6 const int inf=1<<29; 7  8 int dp[40][maxn]; 9 int d[maxn];10 int dis[maxn][maxn];11 int n,k;12 13 int main()14 {15     int cas=0;16     while(scanf("%d%d",&n,&k)!=EOF)17     {18         if(n==0&&k==0) break;19         memset(dis,0,sizeof(dis));20         for(int i=1; i<=n; i++)21         {22            scanf("%d",&d[i]);23         }24         for(int i=1; i<=k; i++)25         {26             for(int j=i; j<=n; j++)27             {28                 dp[i][j]=inf;29             }30         }31         for(int i=1; i<=n; i++)32         {33             for(int j=i; j<=n; j++)34             {35                 for(int c=i; c<=j; c++)36                 dis[i][j]+=abs(d[c]-d[(i+j)/2]);37             }38             dp[1][i]=dis[1][i];39         }40         for(int i=2; i<=k; i++)41         {42             for(int j=i; j<=n; j++)43             {44                 for(int c=i-1; c<=j-1; c++)45                 {46                     dp[i][j]=min(dp[i][j],dp[i-1][c]+dis[c+1][j]);47                 }48             }49         }50         printf("Chain %d\n",++cas);51         printf("Total distance sum = %d\n\n",dp[k][n]);52     }53     return 0;54 }
View Code

 


联系
我们