题目描述

Description

John养了一只叫Joseph的奶牛。一次她去放牛，来到一个非常长的一片地，上面有N块地方长了茂盛的草。我们可
以认为草地是一个数轴上的一些点。Joseph看到这些草非常兴奋，它想把它们全部吃光。于是它开始左右行走，吃
草。John和Joseph开始的时候站在p位置。Joseph的移动速度是一个单位时间一个单位距离。不幸的是，草如果长
时间不吃，就会腐败。我们定义一堆草的腐败值是从Joseph开始吃草到吃到这堆草的总时间。Joseph可不想吃太腐
败的草，它请John帮它安排一个路线，使得它吃完所有的草后，总腐败值最小。John的数学很烂，她不知道该怎样
做，你能帮她么？

Input

• Line 1 : Two space-separated integers: N and L. N<=1000
• Lines 2..N+1: Each line contains a single integer giving the position P of a clump (1 <= P <= 1,000,000).

Output

• Line 1: A single integer: the minimum total staleness Bessie can achieve while eating all the clumps.

Sample Input

4 10
1
9
11
19

Sample Output

44

题目分析

区间DP
f[i][j][k]表示 吃完了区间i~j的草 并且此时在区间左/右端点
吃完了区间i~j的草 并且此时在区间左端点的情况 可以是吃完了(i+1)~j的草 并且在区间左端点 从i+1走到i 也可以是 可以是吃完了(i+1)~j的草 并且在区间右端点 再从j走回到i
右端点同理
尝试了一发记忆化搜索

#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n,p;
int a[1010];
int f[1010][1010][3];
int dfs(int l,int r,int col)
{
    if(f[l][r][col]!=0x3f3f3f3f) return f[l][r][col];
    if(!col) f[l][r][col]=min(dfs(l+1,r,0)+(n-r+l)*(a[l+1]-a[l]),dfs(l+1,r,1)+(n-r+l)*(a[r]-a[l]));
    else f[l][r][col]=min(dfs(l,r-1,1)+(n-r+l)*(a[r]-a[r-1]),dfs(l,r-1,0)+(n-r+l)*(a[r]-a[l]));
    return f[l][r][col]; 
}
int main()
{
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++)
        f[i][i][0]=f[i][i][1]=n*abs(a[i]-p);
    printf("%d",min(dfs(1,n,0),dfs(1,n,1)));
}