首页 > 代码库 > BZOJ 4884 [Lydsy2017年5月月赛]太空猫（单调DP）
BZOJ 4884 [Lydsy2017年5月月赛]太空猫（单调DP）
【题目链接】 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;}BZOJ 4884 [Lydsy2017年5月月赛]太空猫（单调DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。