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

2018.10.22 bzoj1742: Grazing on the Run 边跑边吃草(区间dp)

程序员文章站 2022-04-02 10:06:20
...

传送门
区间dp入门题。


可以想到当前吃掉的草一定是一个区间(因为经过的草一定会吃掉)。
然后最后一定会停在左端点或者右端点。
f[i][j][0/1]f[i][j][0/1]表示已经吃了[i,j][i,j]的草,最后停在左/右端点。
利用费用提前计算的思想转移就行了。
代码:

#include<bits/stdc++.h>
#define N 1005
#define ll long long
using namespace std;
ll f[N][N][2],l,pos[N];
int n;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
int main(){
	n=read(),l=read();
	for(int i=1;i<=n;++i)pos[i]=read();
	pos[++n]=l;
	sort(pos+1,pos+n+1);
	for(int i=1;i<=n;++i)f[i][i][0]=f[i][i][1]=abs(l-pos[i])*n;
	for(int len=2;len<=n;++len){
		for(int i=1;i<=n-len+1;++i){
			int j=i+len-1;
			f[i][j][0]=min(f[i+1][j][0]+(n-len+1)*(pos[i+1]-pos[i]),f[i+1][j][1]+(n-len+1)*(pos[j]-pos[i]));
			f[i][j][1]=min(f[i][j-1][0]+(n-len+1)*(pos[j]-pos[i]),f[i][j-1][1]+(n-len+1)*(pos[j]-pos[j-1]));
		}
	}
	cout<<min(f[1][n][0],f[1][n][1]);
	return 0;
}