欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BZOJ 1742 [Usaco2005 nov]Grazing on the Run 边跑边吃草【区间DP】

程序员文章站 2022-04-02 10:03:00
...

这道题就当做复习区间DP的板子题吧QvQ

f[i][j][0/1]f[i][j][0/1]表示当前已经吃完了区间[i,j][i,j]内的草并且当前停留在最左边与最右边

方程随便推一下就出来了QvQ:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define db double
#define sg string
#define ll long long
#define rep(i,x,y) for(ll i=(x);i<=(y);i++)
#define red(i,x,y) for(ll i=(x);i>=(y);i--)
using namespace std;

const ll N=1e3+5;
const ll Inf=1e18;

ll n,m,p[N],f[N][N][2];

inline ll read() {
    ll x=0;char ch=getchar();bool f=0;
    while(ch>'9'||ch<'0'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?-x:x;
}

int main() {
	n=read(),m=read();
	
	rep(i,1,n) p[i]=read();
	
	p[++n]=m;
	
	sort(p+1,p+1+n);
	
	rep(i,1,n) f[i][i][0]=f[i][i][1]=abs(m-p[i])*n;
	
	rep(len,2,n) rep(i,1,n+1-len) {
		ll j=i+len-1;
		f[i][j][0]=min(f[i+1][j][0]+(p[i+1]-p[i])*(n-j+i),f[i+1][j][1]+(p[j]-p[i])*(n-j+i));
		f[i][j][1]=min(f[i][j-1][0]+(p[j]-p[i])*(n-j+i),f[i][j-1][1]+(p[j]-p[j-1])*(n-j+i));
	}
	
	printf("%lld\n",min(f[1][n][0],f[1][n][1]));

	return 0;
}