NOIP2014飞扬的小鸟

题目描述

Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度,让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话,便宣告失败。

为了简化问题,我们对游戏规则进行了简化和改编:
游戏界面是一个长为n ,高为 m 的二维平面,其中有k 个管道(忽略管道的宽度)。

小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发,到达游戏界面最右边时,游戏完成。

小鸟每个单位时间沿横坐标方向右移的距离为1 ,竖直移动的距离由玩家控制。如果点击屏幕,小鸟就会上升一定高度X ,每个单位时间可以点击多次,效果叠加;
如果不点击屏幕,小鸟就会下降一定高度Y 。小鸟位于横坐标方向不同位置时,上升的高度X 和下降的高度Y 可能互不相同。

小鸟高度等于0 或者小鸟碰到管道时,游戏失败。小鸟高度为 m 时,无法再上升。
现在,请你判断是否可以完成游戏。如果可以 ,输出最少点击屏幕数;否则,输出小鸟最多可以通过多少个管道缝隙。

输入输出格式

输入格式:
输入文件名为 bird.in 。

第1 行有3 个整数n ,m ,k ,分别表示游戏界面的长度,高度和水管的数量,每两个

整数之间用一个空格隔开;

接下来的n 行,每行2 个用一个空格隔开的整数X 和Y ,依次表示在横坐标位置0 ~n- 1

上玩家点击屏幕后,小鸟在下一位置上升的高度X ,以及在这个位置上玩家不点击屏幕时,

小鸟在下一位置下降的高度Y。

接下来k 行,每行3 个整数P ,L ,H ,每两个整数之间用一个空格隔开。每行表示一

个管道,其中P 表示管道的横坐标,L 表示此管道缝隙的下边沿高度为L ,H 表示管道缝隙

上边沿的高度(输入数据保证P 各不相同,但不保证按照大小顺序给出)。

输出格式:
输出文件名为bird.out 。

共两行。

第一行,包含一个整数,如果可以成功完成游戏,则输出1 ,否则输出0 。

第二行,包含一个整数,如果第一行为1 ,则输出成功完成游戏需要最少点击屏幕数,否则,输出小鸟最多可以通过多少个管道缝隙。

输入输出样例

输入样例#1:

10 10 6
3 9
9 9
1 2
1 3
1 2
1 1
2 1
2 1
1 6
2 2
1 2 7
5 1 5
6 3 5
7 5 8
8 7 9
9 1 3

输出样例#1:
1
6

输入样例#2:

10 10 4
1 2
3 1
2 2
1 8
1 8
3 2
2 1
2 1
2 2
1 2
1 0 2
6 7 9
9 1 4
3 8 10

输出样例#2:
0
3

说明

【输入输出样例说明】

如下图所示,蓝色直线表示小鸟的飞行轨迹,红色直线表示管道。

图片

【数据范围】

对于30% 的数据:5 ≤ n ≤ 10,5 ≤ m ≤ 10,k = 0 ,保证存在一组最优解使得同一单位时间最多点击屏幕3 次;

对于50% 的数据:5 ≤ n ≤ 2 0 ,5 ≤ m ≤ 10,保证存在一组最优解使得同一单位时间最多点击屏幕3 次;

对于70% 的数据:5 ≤ n ≤ 1000,5 ≤ m ≤ 1 0 0 ;

对于100%的数据:5 ≤ n ≤ 100 0 0 ,5 ≤ m ≤ 1 0 00,0 ≤ k < n ,0<X < m ,0<Y <m,0<P <n,0 ≤ L < H ≤ m ,L +1< H 。

题目分析

关于这道题,其实从题目中可以多点几次这个信息,可以很容易联想到完全背包,而且数据规模可以容许使用动态规划。
我们可以令f[i][j]表示到第i列j行最少需要点击屏幕的次数。
对于一个点(i,j)可以从i-1列的(i-1,j-up[i-1])、(i-1,j+down[i-1])转移过来。
同时根据完全背包,我们也可以从(i,j-up[i-1])转移,但要注意的是,即使是当前行的管道位置,我们也必须将其更新,因为它可能会对同一列的上方的位置产生影响,否则会影响同一列点击屏幕多次的状态。
同时,如果我们要用同一列的点来更新它的话,那么另一个点一定是从前一列的点向上跳得到,否则不能用来表示多次点击屏幕累计效果。
对于一列的最高点,我们要将它特殊处理,因为他可以是碰到顶部无法上升而得到,所以要对它进行多次更新。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# include <algorithm>
# include <iostream>
# include <cstdio>
# include <cstring>
# include <queue>
# define R register
# define LL long long
# define inf 999999999

using namespace std;

int n,m,up[10010],down[10010],a[10010],b[10010],f[10010][1010],k,gd[10010],g;

inline int in(R int &a){
R char c = getchar();R int x = 0,f = 1;
while(!isdigit(c)){if(c == '-') f = -1;c = getchar();}
while(isdigit(c)) x = x*10+c-'0',c = getchar();
a = x*f;
}

int main (){
in(n),in(m),in(k);
n++;//整体往后挪一位
for(R int i=2; i<=n; ++i)
for(R int j=0; j<=m+1; ++j)
f[i][j] = inf;//初始化
for(R int i=1; i<n; ++i) in(up[i]),in(down[i]);
for(R int i=1; i<=n; ++i) b[i] = m+1;
for(R int i=1; i<=k; ++i) {
R int d,x,y;
in(d),in(x),in(y);
gd[++g] = d+1;
a[d+1] = x,b[d+1] = y;
}
sort(gd+1,gd+g+1);
for(R int i=1; i<=m; ++i) f[1][i]=0;
for(R int i=2; i<=n; ++i){
for(R int j=1; j<=m; ++j){
if(j-up[i-1] > 0)
f[i][j] = min(f[i][j],f[i-1][j-up[i-1]]+1),
f[i][j] = min(f[i][j],f[i][j-up[i-1]]+1);
}//往上跳

for(R int j=m-up[i-1]; j<=m; ++j)
if(j > 0)
f[i][m] = min(f[i][m],f[i-1][j]+1),
f[i][m] = min(f[i][m],f[i][j]+1);
//顶部特殊处理
for(R int j=a[i]+1; j<b[i]; ++j)
if(j+down[i-1] <= m) f[i][j] = min(f[i][j],f[i-1][j+down[i-1]]);
//往下降

for(R int j=1; j<=a[i]; ++j) f[i][j] = inf;
for(R int j=b[i]; j<=m; ++j) f[i][j] = inf;
//将不合法状态重新赋值回去
}

R int ans = inf;

for (R int i=a[n]+1; i<b[n]; ++i) ans = min(ans,f[n][i]);

if(ans < inf) printf("1\n%d",ans);
else{
R int i = 1;
for(; i<=g; ++i)
for(R int j=a[gd[i]]+1; j<b[gd[i]]; ++j){
if(f[gd[i]][j] < inf) break;
if(j == b[gd[i]]-1){
printf("0\n%d",i-1);
return 0;
}
}
}
return 0;
}

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. 题目描述
  2. 2. 说明
    1. 2.0.1. 【输入输出样例说明】
    2. 2.0.2. 【数据范围】
  • 3. 题目分析
  • 4. 代码
  • ,