[文章目录]
Description
给你一个数轴，有n个位置,p1~pn。你的初始位置为L。每一秒，当前存在的未达到的位置的代价+1。每一秒你能走一个单位。到达一个位置的时候，可以将该位置删掉，花费相应的代价。询问将所有位置都删掉的最小代价。n<=1000 p<=10^6
区间DP。
一旦走到一个存在的位置肯定删除，那么每个时刻删除的区间一定是连续的一段，并且包含L。
设dp[i][j]表示第i个位置到底j个位置都删掉了的最小代价。当前在第i个位置。转移两种情况，i->i-1 i->j+1。
发现转移的时候并不知道当前时间。发现统计代价的方式可以转换一下，表示所有点的代价和（不管是否存在）。转移的时候累加时间乘以当前存在的点的个数。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,L,pos[1010];
ll dp[1010][1010];
inline ll Abs(ll x){return x>0?x:-x;}
int main()
{
scanf("%d%d",&n,&L);
for(int i=1;i<=n;++i) scanf("%d",pos+i);
sort(pos+1,pos+n+1); memset(dp,0x3f,sizeof dp);
int l=1,r=n+1,mid;
while(l<r)
{
mid=(l+r)>>1;
if(pos[mid]>=L) r=mid;
else l=mid+1;
}
if(r<=n&&r>=1&&pos[r]>=L) dp[r][r]=Abs(pos[r]-L)*n;
if(r-1<=n&&r-1>=1&&pos[r-1]<L) dp[r-1][r-1]=Abs(pos[r-1]-L)*n;
for(int i=0;i<n;++i)
{
for(int j=1;j+i<=n;++j)
{
if(j!=1)
{
dp[j-1][j+i]=min(dp[j-1][j+i],dp[j][j+i]+Abs(pos[j]-pos[j-1])*(n-i-1));
dp[j-1][j+i]=min(dp[j-1][j+i],dp[j+i][j]+Abs(pos[j+i]-pos[j-1])*(n-i-1));
}
if(j+i!=n)
{+
dp[j+i+1][j]=min(dp[j+i+1][j],dp[j][j+i]+Abs(pos[j]-pos[j+i+1])*(n-i-1));
dp[j+i+1][j]=min(dp[j+i+1][j],dp[j+i][j]+Abs(pos[j+i]-pos[j+i+1])*(n-i-1));
}
}
}
printf("%lld",min(dp[1][n],dp[n][1]));
return 0;
}