首页 > 代码库 > hdu 1227 Fast Food
hdu 1227 Fast Food
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。