奶牛吃草

奶牛吃草

时间限制：4 sec

空间限制：256 MB

问题描述

有一只奶牛在一条笔直的道路上（可以看做是一个数轴）。初始，它在道路上坐标为 K

的地方。

这条道路上有 n 棵非常新鲜的青草（编号从 1 开始）。其中第 i 棵青草位于道路上坐标为 x[i] 的地方。贝西每秒钟可以沿着道路的方向向前（坐标加）或向后（坐标减）移动一个坐标单位的距离。

它只要移动到青草所在的地方，就可以一口吞掉青草，它的食速很快，吃草的时间可以不计。

它要吃光所有的青草。不过，青草太新鲜了，在被吞掉之前，暴露在道路上的每棵青草每秒种都会损失一单位的口感。

请你帮它计算，该怎样来回跑动，才能在口感损失之和最小的情况下吃掉所有的青草。

输入格式

第一行两个用空格隔开的整数 n,k，分别表示青草的数目和奶牛的初始坐标。第 2 行到第 n+1 行，第 i+1 行有一个整数 x[i]，描述第 i 棵青草的坐标。

输格式

一行一个整数，表示吃掉所有青草的前提下，最小损失的口感之和。保证答案在 32 位有符号整数的范围内。

样例输入

样例输

样例解释

先跑到 9，然后跑到 11，再跑到 19，最后到 1，可以让损失的口感总和为29+1+3+11=44。可以证明不存在比这更优的解。

数据范围

对于 50% 的数据，保证 1≤n≤4，1≤k,x[i]≤20。 对于 80% 的数据，保证 1≤n≤100。 对于 100% 的数据，保证 1≤n≤1000，1≤k,x[i]≤10^6。

提示

[我们先从另一个角度看答案，即损失的总口感：从初始状态到奶牛吃掉第 1 棵草之间的时间（我们在下面把它叫做第 1 段时间），所有的 n 棵青草都在流失口感；……；从奶牛吃掉第 i 棵草到它吃掉第 i+1 棵草之间的时间（我们在下面把它叫做第 i+1 段时

间），还没有被吃掉的 n-i 棵草都在流失口感；……]

[于是我们发现，第 i 段时间对答案的贡献，为这段时间的长度与 n-i+1 的乘积。]

[接着，我们再来关注最优策略。吃完一棵草后（包括初始时），奶牛的最优策略一定是直奔另一棵草。]

[由于奶牛不会飞，所以奶牛走过的所有路一定是一段连续的区间。] [显然地，被奶牛经过过的地方，按最优策略，一定不会留下青草。]

[所以我们可以**将所有青草的坐标排序**（下面我们都使用排完序后的编号），然后用dp[l][r][j] 表示吃完 [l,r] 范围内的青草时的最小答案，j 只有 0,1 两种取值，分别表示奶牛吃完最后一棵草停在青草 l 还是 r 上（只有可能是这两种情况，否则与上面的结论矛盾）。]

[于是我们就可以轻易地设计出状态转移方程：]

[dp[l][r][0]=min(dp[l+1][r][0]+(n-r+l)*abs(x[l]-x[l+1]),dp[l+1][r][1]+(n-r+l)*abs(x[l]-x[r]))]

[dp[l][r][1]=min(dp[l][r-1][1]+(n-r+l)*abs(x[r]-x[r-1]),dp[l][r-1][0]+(n-r+l)*abs(x[r]-x[l]))]

[边界为：dp[i][i][j]=abs(x[i]-k)*n（对于所有 1<=i<=n，j=0,1）] [友情提示：请注意枚举顺序。]

代码

#include<iostream> #include<vector> #include<algorithm>

#pragma warning(disable:4996) using namespace std;

const int N = 2000;

//dp:DP数组，dp[l][r][j]表示吃完[l,r]范围内的青草时的最小答案，j只有0，1两种取值，分别表示奶牛吃完最后一颗草停留在青草l或r上

int dp[N + 2][N + 2][2];

// 本函数求解答案（损失的最小口感和）

// n：青草棵数

// k：奶牛的初始坐标

// x：描述序列 x（这里需要注意的是，由于 x 的下标从 1 开始，因此 x[0] 的值为 -1，你可以忽略它的值，只需知道我们从下标 1 开始存放有效信息即可），意义同题目描述

// 返回值：损失的最小口感和

int getAnswer(int n, int k, vector<int> x) {

sort(x.begin() + 1, x.end());

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

dp[i][i][0] = dp[i][i][1] = abs(x[i] - k) * n;//设置边界条件：只吃一棵草的情况下，答案应该是什么呢？

for (int len = 1; len < n; ++len)

for (int l = 1, r; (r = l + len) <= n; ++l) {

//枚举空间（先枚举区间长度，再枚举左端点，求出右端点）

//进行转移

dp[l][r][0] =

min(dp[l + 1][r][0] + (n - r + l)* abs(x[l] - x[l + 1]),

dp[l + 1][r][1] + (n - r + l)* abs(x[l] - x[r]));

dp[l][r][1] =

min(dp[l][r - 1][1] + (n - r + l)* abs(x[r] - x[r - 1]),

dp[l][r - 1][0] + (n - r + l)* abs(x[r] - x[l]));

}

return min(dp[1][n][0], dp[1][n][1]);

}

int main()

{

int n, k,tmp;

scanf("%d%d", &n,&k);

vector<int> x;

x.emplace_back(-1);

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

{

scanf("%d", &tmp);

x.emplace_back(tmp);

}

int ans = getAnswer(n,k,x);

printf("%d\n", ans);

return 0;

}