Skip to content

11230: 【原1230】Restaurant

题目

题目描述

author: Yanqing Peng 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1230

Description

一家餐饮连锁公司在一条公路上设有若干个餐厅。我们用一条坐标轴来描述这条公路,每一个餐厅的坐标都是整数,没有两个餐厅坐标相同。两个餐厅之间的距离,定义为它们坐标值差的绝对值。我们需要在一些餐厅内设立仓库————当然,并不是每一个餐厅内都必须设立仓库,仓库必须被建在餐厅里,因此它的坐标和它所在的餐厅坐标相同。每个餐厅会到距离它最近的仓库获取食品原料,建立这些仓库的原则是:所有餐厅到各自获取原料的仓库的距离总和最小。

你的任务是编写一个程序,在给定了每个餐厅的坐标和将要建立的仓库数之后,按照上述原则,合理地选择这些仓库的位置。

Input Format

输入的第一行包含两个整数:第一个整数是餐厅的数目N,第二个整数是将建立的仓库数P。

输入的第二行以递增顺序给出了N个整数,这N个整数分别表示各餐厅的位置坐标。

Output Format

输出文件仅包含一个整数,为所求距离和的最小值。

Sample Input

10 5
1 2 3 6 7 9 11 22 44 50

Sample Output

9

Limits

对于30%的数据,N<=300,P<=3

对于80%的数据,N<=300,P<=30

对于100%的数据,N<=2000, P<N

计算中涉及到的一切整数及最终答案均保证不超过10^9。

Time Limit: 1000ms

Memory Limit: 65536kb

Hint

尝试使用动态规划解题。

yyong119's solution

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAX_N 2010
using namespace std;

int a[MAX_N];
int dp[MAX_N][MAX_N];
int w[MAX_N][MAX_N];
int n, m;

int main() {

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);

    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            w[i][j] = w[i][j - 1] + a[j] - a[(i + j) >> 1];

    memset(dp, INF, sizeof(dp));
    //dp[i][j]前i位建j个仓库
    for (int i = 1; i <= n; ++i) {
        dp[i][1] = w[1][i];
        dp[i][i] = 0;
    }

    // for (int i = 1; i <= n; ++i) //末仓库位置 
    //     for (int j = 2; j <= min(m, i); ++j) //仓库数
    //         for(int k = i - 1; k >= j - 1 && w[k + 1][i] < dp[i][j];--k) //k到i建1仓库
    //以上注释可过80分,区别仅在ij层循环次序
    //比赛碰到就随缘80或100吧
    for (int i = 2; i <= m; ++i) //仓库数
        for (int j = i + 1; j <= n - m + i; ++j) //末仓库位置
            for (int k = j - 1; k >= i - 1 && w[k + 1][j] < dp[j][i]; --k) //k到j建1仓库
                dp[j][i] = min(dp[j][i], dp[k][i - 1] + w[k + 1][j]);

    printf("%d\n", dp[n][m]);
    return 0;
}