BZOJ 4884 [Lydsy2017年5月月赛]太空猫(单调DP)
2024-09-02 20:54:11
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=4884
【题目大意】
太空猫(SpaceCat)是一款画面精致、玩法有趣的休闲游戏,
你需要控制一只坐在迷你飞碟上的猫咪在太空里不断探索,让大家看看你能飞得多远。
游戏地图可以看成一个二维的网格图,上下是两段障碍物。
在游戏的一开始,太空猫位于地图最左边的下边界之上,且重力方向向下。
在每个时刻,你可以用手指点击屏幕,翻转重力的方向,
或者通过遥感控制太空猫往左或往右移动。每次翻转重力方向时,
你需要消耗的能量值等于上下底边之间的高度差。
在左右移动的时候,太空猫可以下降到对应重力方向更低的位置,但不能往上爬。
当然,太空猫也不能穿墙而过。在重力翻转的过程中,
直到碰到地面之前,你都不能操控太空猫左右移动。
太空猫的终点位于地图的最右端的下底边之上,
请计算为了让太空猫到达终点,需要消耗最小能量,如果不能到达请输出-1
【题解】
我们用dp[i][j]表示到第i个位置,重力方向为j时候的最小能量消耗,
对于不可达要在每个位置特殊判断是否存在c[i]<=f[i-1]或者f[i]>=c[i-1]的情况。
【代码】
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=100010;
int n,c[N],f[N];
LL dp[N][2];
const LL INF=0x3f3f3f3f3f3f3f3f;
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
for(int i=1;i<=n;i++)scanf("%d",&f[i]);
memset(dp,0x3f,sizeof(dp));
dp[1][0]=0; dp[1][1]=c[1]-f[1];
for(int i=2;i<=n;i++){
if(f[i]<=f[i-1])dp[i][0]=dp[i-1][0];
if(c[i]>=c[i-1])dp[i][1]=dp[i-1][1];
dp[i][0]=min(dp[i][0],dp[i][1]+c[i]-f[i]);
dp[i][1]=min(dp[i][1],dp[i][0]+c[i]-f[i]);
if(c[i]<=f[i-1]||f[i]>=c[i-1])dp[i][0]=dp[i][1]=INF;
}printf("%lld\n",dp[n][0]==INF?-1:dp[n][0]);
}return 0;
}
最新文章
- 【6年开源路】FineUI家族今日全部更新(FineUI + FineUI3to4 + FineUI.Design + AppBox)!
- 关于 window.parent, window.top, window.self 详解
- Spring框架IOC容器和AOP解析
- 打造H5里的“3D全景漫游”秘籍
- No.013:Roman to Integer
- 【2016-10-12】【坚持学习】【Day3】【责任链模式】
- c#语句 习题
- UNION并集运算
- JPA一对多关联
- [Java A] – is not an enclosing class
- 【BZOJ】【1965】SHUFFLE 洗牌
- LightOJ_1038 Race to 1 Again
- 【转】ASP.NET MVC 入门教程列表
- Android - 位置定位(Location)服务(Service)类的基本操作
- RTMPdump(libRTMP) 源代码分析 7: 建立一个流媒体连接 (NetStream部分 2)
- PHP Array 简介
- Spring MVC(四)文件上传
- 微信小程序 加载图片时,先拉长,再恢复正常
- CSS 背景图像 填充整个页面示例
- Python开发一个多并发的FTP SERVER