2018.10.22 bzoj1742: Grazing on the Run 边跑边吃草(区间dp)
2024-08-24 19:01:12
传送门
区间dp入门题。
可以想到当前吃掉的草一定是一个区间(因为经过的草一定会吃掉)。
然后最后一定会停在左端点或者右端点。
f[i][j][0/1]f[i][j][0/1]f[i][j][0/1]表示已经吃了[i,j][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;
}
最新文章
- MongoDB C# / .NET Driver
- Object-C 基础笔记3---属性
- CentOS6 root 用户 vi/vim 无法开启高亮
- [Linux]关机和重启命令
- CentOS 6.5 安装MySQL5.7 RPM
- SaltStack 介绍和安装
- ubuntu 配置minicom 进行串口开发
- PAT基础6-12
- 进程描述和控制(os 笔记二)
- 【转载】 大龄码农那些事——也谈996.ICU
- 浅谈 foreach 的原理
- 【刷题】LOJ 6005 「网络流 24 题」最长递增子序列
- centos chroot使用
- OC MRC之autorelease问题(代码分析)
- ajax传递的参数服务器端接受不到的原因
- JavaWeb -jsp文件和内置对象的解析
- 服务遇到错误。很可能由IncludeExceptionDetailInFaults=true创建的ExceptionDetail,其值为:System.ArgumentException:指定的值还有无效的控制字符
- es第二篇:Document APIs
- windows10 自带的OpenSSH Client(Beta)
- Django - ModelForm组件