首页 > 代码库 > hdu1227 Fast Food
hdu1227 Fast Food
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1227
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string.h> #include <string> using namespace std; const int MAXN = 200 + 1; //the number of restaurants const int MAXM = 30 + 1; //the number of depots int dp[MAXN][MAXM], value[MAXN][MAXN], pos[MAXN]; int n, k; //输入值 /* dp[i][j]表示在i个饭店之间建设j个仓库的最短距离, value[i][j]表示在第i个饭店与第j个饭店之间建设一个仓库, 并由这个仓库供给i到j之间的饭店(包括i,j)的最短距离。 很明显这个仓库需要建设在i与j的中位数旁边即mid = (i + j) / 2; 当i到j之间有奇数个饭店时mid = i到j最中间的点, 当i到j之间有偶数个饭店时mid = i到j之间最中间的两点的左边的 一点(右边的一个点也可以,其实只要是这两个点之间的点都可以) pos[]数组存每个输入饭店的位置。 */ void input() { int cases = 0; while (scanf("%d %d", &n, &k) != EOF) //输入 { if (!n && !k) break; int mid = 0; for (int i = 1; i <= n; i++) { scanf("%d", &pos[i]); } for (int i = 1; i <= n; i++) //计算value[][]数组 { for (int j = i; j <= n; j++) { mid = (i + j) / 2; value[i][j] = 0; for (int x = i; x <= j; x++) { value[i][j] += abs(pos[x] - pos[mid]); } } } for (int i = 1; i <= n; i++) dp[i][1] = value[1][i]; for (int i = 1; i <= n; i++) //计算dp[][]; { for (int j = 2; j <= i && j <= k; j++) { dp[i][j] = dp[i - 1][j - 1]; //赋初值,直接在第i个饭店处放置一个仓库 for (int x = j - 1; x < i; x++) //k的范围 { if (dp[x][j - 1] + value[x + 1][i] < dp[i][j]) { dp[i][j] = dp[x][j - 1] + value[x + 1][i]; } } } } printf("Chain %d\n", ++cases); //输出 printf("Total distance sum = %d\n\n", dp[n][k]); } } int main() { input(); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。