首页 > 代码库 > 【BZOJ4884】太空猫 [DP]

【BZOJ4884】太空猫 [DP]

2024-09-20 08:37:40   218人阅读

太空猫

Time Limit: 1 Sec  Memory Limit: 256 MB
[Submit][Status][Discuss]

Description

　　太空猫(SpaceCat)是一款画面精致、玩法有趣的休闲游戏，你需要控制一只坐在迷你飞碟上的猫咪在太空里不断探索，让大家看看你能飞得多远。
　　游戏地图可以看成一个二维的网格图，上下是两段障碍物。
　　在游戏的一开始，太空猫位于地图最左边的下边界之上，且重力方向向下。
　　在每个时刻，你可以用手指点击屏幕，翻转重力的方向，或者通过遥感控制太空猫往左或往右移动。
　　每次翻转重力方向时，你需要消耗的能量值等于上下底边之间的高度差。
　　在左右移动的时候，太空猫可以下降到对应重力方向更低的位置，但不能往上爬。
　　当然，太空猫也不能穿墙而过。在重力翻转的过程中，直到碰到地面之前，你都不能操控太空猫左右移动。
　　太空猫的终点位于地图的最右端的下底边之上，请计算为了让太空猫到达终点，需要消耗能量的最小值。
　　技术分享

Input

　　第一行包含一个正整数n，即地图的宽度。
　　第二行包含n个正整数c_1,c_2,...,c_n，分别表示每个横坐标对应的上边界的高度。
　　第三行包含n个正整数f_1,f_2,...,f_n，分别表示每个横坐标对应的下边界的高度。

Output

　　输出一行一个整数，即最少的能量，若无法到达终点，请输出“-1”。

Sample Input

　　4
　　3 4 3 2
　　1 2 1 1

Sample Output

　　4

HINT

　　1<=n<=100000, 2<=c_i<=10^9, 1<=f_i<c_i

Solution

　　很简单的DP，我们令 f[i][0/1]表示 到达第 i 个位置，重力方向为 向上/向下 的最小花费。

　　然后转移显然，可以参考程序。

Code

技术分享
 1 #include<iostream>   2 #include<string>   3 #include<algorithm>   4 #include<cstdio>   5 #include<cstring>   6 #include<cstdlib>   7 #include<cmath> 8 using namespace std; 9 typedef long long s64;10 11 const int ONE = 1000001;12 13 int n;14 int a[ONE],b[ONE];15 s64 f[ONE][2];16 17 inline s64 get()18 {19         s64 res=1,Q=1;  char c;20         while( (c=getchar())<48 || c>57)21         if(c==‘-‘)Q=-1;22         if(Q) res=c-48; 23         while((c=getchar())>=48 && c<=57) 24         res=res*10+c-48;25         return res*Q; 26 }27 28 int main()29 {30         n=get();31         for(int i=1;i<=n;i++) a[i]=get(), f[i][0]=1e18L;32         for(int i=1;i<=n;i++) b[i]=get(), f[i][1]=1e18L;33         34         f[1][0] = 0;    f[1][1] = a[1]-b[1];35         36         for(int i=2;i<=n;i++)37         {38             if(a[i-1] <= a[i]) f[i][1] = f[i-1][1];39             if(b[i-1] >= b[i]) f[i][0] = f[i-1][0]; 40             41             if(a[i-1] <= b[i] || b[i-1] >= a[i]) {printf("-1"); exit(0);}42             43             f[i][0] = min(f[i][0], f[i][1] + a[i]-b[i]);44             f[i][1] = min(f[i][1], f[i][0] + a[i]-b[i]);45             46         }47         48         printf("%lld",f[n][0]==1e18 ? -1:f[n][0]);49 }
View Code

 

【BZOJ4884】太空猫 [DP]


联系
我们