# tioj 1090 Grazing on the Run

https://tioj.ck.tp.edu.tw/problems/1090

很像joi本選某一題，很久以前看過但當時不會，然後現在也忘了哪一題了qq

* 簡單來說就是設定他的左右界以及他停在哪裡，所以可以定一個dp狀態為：
* dp[i][j][0/1] = 吃掉i到j之間的蘋果(假設蘋果已排序)，並且停留在左邊或右邊(分別是0/1)

轉移：

int left=n-(j-i);
dp[i][j][0]=min(dp[i+1][j][0]+abs(pt[i]-pt[i+1])*left, dp[i+1][j][1]+abs(pt[i]-pt[j])*left);
dp[i][j][1]=min(dp[i][j-1][0]+abs(pt[j]-pt[i])*left, dp[i][j-1][1]+abs(pt[j]-pt[j-1])*left);
// left為剩下多少蘋果沒被吃掉
// abs(pt[x]-pt[y])要乘以left因為對之後的left個蘋果都會貢獻abs(pt[x]-pt[y])的不新鮮度，所以先把他算起來

* 記得dp[i][i][0/1]的base case

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
using namespace std;
typedef pair<long long,long long> pll;
typedef pair<int,int> pii;
typedef long long ll;

ll dp[1010][1010][2]={0};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, l;
    cin>>n>>l;
    vector<ll> pt(n+1, 0);
    rep(i,1,n+1) cin>>pt[i];
    sort(ALL(pt));
    for(int i=1;i<=n;++i) dp[i][i][0]=dp[i][i][1]=abs(pt[i]-l)*n;
    for(int k=2;k<=n;++k){
        for(int i=1;i+k-1<=n;++i){
            int j=i+k-1;
            int left=n-(j-i);
            dp[i][j][0]=min(dp[i+1][j][0]+abs(pt[i]-pt[i+1])*left, dp[i+1][j][1]+abs(pt[i]-pt[j])*left);
            dp[i][j][1]=min(dp[i][j-1][0]+abs(pt[j]-pt[i])*left, dp[i][j-1][1]+abs(pt[j]-pt[j-1])*left);
            // cout<<i<<" "<<j<<" "<<dp[i][j][0]<<" "<<dp[i][j][1]<<NL;
        }
    }
    cout<<min(dp[1][n][0], dp[1][n][1])<<NL;
}