2018.10.22 bzoj1742: Grazing on the Run 边跑边吃草(区间dp)
程序员文章站
2022-04-02 10:06:20
...
传送门
区间dp入门题。
可以想到当前吃掉的草一定是一个区间(因为经过的草一定会吃掉)。
然后最后一定会停在左端点或者右端点。
表示已经吃了的草,最后停在左/右端点。
利用费用提前计算的思想转移就行了。
代码:
#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;
}
下一篇: 计算几何-----》两直线是否相交
推荐阅读
-
bzoj 1694 && 1742: [Usaco2005 nov]Grazing on the Run 边跑边吃草(DP)
-
[Usaco2005 nov]Grazing on the Run 边跑边吃草 BZOJ1742
-
2018.10.22 bzoj1742: Grazing on the Run 边跑边吃草(区间dp)
-
bzoj 1742: [Usaco2005 nov]Grazing on the Run 边跑边吃草【区间dp】
-
[bzoj1742][Usaco2005 nov][DP]Grazing on the Run 边跑边吃草
-
BZOJ 1742 [Usaco2005 nov]Grazing on the Run 边跑边吃草【区间DP】