「NOIP14 D1T3」飞扬的小鸟

Source and Judge

NOIP2014 提高组 D1T3
Luogu1941
Caioj1565

Problem

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


为了简化问题,我们对游戏规则进行了简化和改编:
1. 游戏界面是一个长为 n ,高为 m 的二维平面,其中有 k 个管道(忽略管道的宽度)。
2. 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发,到达游戏界面最右边时,游戏完成。
3. 小鸟每个单位时间沿横坐标方向右移的距离为1 ,竖直移动的距离由玩家控制。如果点击屏幕,小鸟就会上升一定高度X ,每个单位时间可以点击多次,效果叠加;如果不点击屏幕,小鸟就会下降一定高度Y 。小鸟位于横坐标方向不同位置时,上升的高度X 和下降的高度Y 可能互不相同。
4. 小鸟高度等于0 或者小鸟碰到管道时,游戏失败。小鸟高度为 m 时,无法再上升。

现在,请你判断是否可以完成游戏。
如果可以 ,输出最少点击屏幕数;否则,输出小鸟最多可以通过多少个管道缝隙。
「Input」
第1 行有3 个整数n ,m ,k ,分别表示游戏界面的长度,高度和水管的数量,每两个整数之间用一个空格隔开;
接下来的n 行,每行2 个用一个空格隔开的整数X 和Y ,依次表示在横坐标位置0 ~n- 1上玩家点击屏幕后,小鸟在下一位置上升的高度X ,以及在这个位置上玩家不点击屏幕时,小鸟在下一位置下降的高度Y 。
接下来k 行,每行3 个整数P ,L ,H ,每两个整数之间用一个空格隔开。
每行表示一个管道,其中P 表示管道的横坐标,L 表示此管道缝隙的下边沿高度为L ,H 表示管道缝隙上边沿的高度(输入数据保证P 各不相同,但不保证按照大小顺序给出)。
「Output」
共两行。
第一行,包含一个整数,如果可以成功完成游戏,则输出1 ,否则输出0 。
第二行,包含一个整数,如果第一行为1 ,则输出成功完成游戏需要最少点击屏幕数,否则,输出小鸟最多可以通过多少个管道缝隙。
「Limited conditions」
对于 30%的数据:5≤n≤10,5≤m≤10,k=0,保证存在一组最优解使得同一单位时间最多点击屏幕 3 次;
对于 50%的数据:5≤n≤20,5≤m≤10,保证存在一组最优解使得同一单位时间最多点击屏幕 3 次;
对于 70%的数据:5≤n≤1000,5≤m≤100;
对于 100%的数据:5≤n≤10000,5≤m≤1000,0≤k<n,0<X<m,0<Y<m,0<P<n,0≤L<H ≤m,L+1<H。
「Sample input 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
「Sample output 1」
1
6
「Sample input 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
「Sample output 2」
0
3
「Sample explanation」
如下图所示,蓝色直线表示小鸟的飞行轨迹,红色直线表示管道。

Record

3h

Analysis1

请先思考后再展开

首先,题意不是很明确,有个细节:当高度达到m以上,并不是非法,而是视作m!
解法1:bfs爆搜
预计得分:75
时间复杂度:$O(nm^2log_2(nm))$

Code1

请先思考后再展开
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
//*******************全局常量*******************
const int MAXN=10001;
//*******************全局定义*******************
int n,m;
int ll[MAXN],rr[MAXN];
int xx[MAXN],yy[MAXN];
struct Pt
{
int x,y,g;
Pt(int tx=0,int ty=0,int tg=0) {x=tx,y=ty,g=tg;}
};
bool operator < (Pt a,Pt b) {return a.g>b.g;}
//*******************实现*******************
priority_queue<Pt> q;//小根堆
int ans2=0;
int vis[MAXN][1001];//min( g() )
void ins(Pt now)
{
if(now.y>ll[now.x] and now.y<rr[now.x] and vis[now.x][now.y]>now.g)
{
vis[now.x][now.y]=now.g;
ans2=mymax(ans2,now.x);
q.push(now);
}
}
int solve()
{
memset(vis,127,sizeof(vis));
for(int i=1;i<=m;i++) ins( Pt(0,i,0) );
while(!q.empty())
{
Pt now=q.top();q.pop();
if(now.g>vis[now.x][now.y]) continue;//old imformation
if(now.x==n) return now.g;
//1. down
ins(Pt(now.x+1,now.y-yy[now.x],now.g));
//2. up
int y=now.y,g=now.g;
while(y<rr[now.x+1])//剪枝
{
y+=xx[now.x];
if(y>m) y=m;
ins( Pt(now.x+1,y,++g) );
if(y==m) break;
}
}
return -1;
}
//*******************主函数*******************
int pp[MAXN];
int main()
{
//freopen("tmp.in","r",stdin);
int k;scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<=n-1;i++) scanf("%d%d",&xx[i],&yy[i]);
memset(ll,0,sizeof(ll));
memset(rr,127,sizeof(rr));
for(int i=1;i<=k;i++)
{
scanf("%d",&pp[i]);
scanf("%d%d",&ll[ pp[i] ],&rr[ pp[i] ]);
}
int ans=solve();
if(ans>=0) printf("1\n%d",ans);
else
{
sort(pp+1,pp+k+1);
printf("0\n%d",lower_bound(pp+1,pp+k+1,ans2)-pp-1);
}
}

Analysis2

请先思考后再展开

在上一个做法中,我们忽略了这道题一个重要的特性:方向固定(向右)
所以是可以dp的
把上升看作「多次背包」,下降看作「单次背包」

朴素的$O(nm^2)$:
$$
f[i][j] =
\left{
\begin{matrix}
\underset{k}{min}(f[i-1][j-k\times x[i-1]])+k& (j-k\times x[i-1]>0) \\
f[i-1][j+y[i-1]]& (j+y[i-1]\leq m)
\end{matrix}
\right.
$$

然鹅,对于这之中耗时最多的枚举k,其实我们完全可以「放后影响」,从上一遍搞过来
(显而易见,打bfs的时候想过但是不适用……然鹅dp是可以的)
于是就下降到了$O(nm)$辣:
$$
f[i][j] =
\left{
\begin{matrix}
min(f[i-1][j-x[i-1]],f[i][j-x[i-1])+1& (j-x[i-1]>0) \\
f[i-1][j+y[i-1]]& (j+y[i-1]\leq m)
\end{matrix}
\right.
$$

注意:
对于撞到管子的$f[i][j]$,还是要计算的,因为有这种情况:
我们从$f[i][j-x[i-1]]$转移过来,它撞墙了,但$f[i][j]$没有撞墙,它去没得继承了。
所以要
顺便说一句:
感觉这个dp很像维护一个二维前缀

所以,综上所述,对于每一列:

  1. 无视水管,dp(特判m的情况),只考虑上升做多重背包
  2. 水管上,还原为inf
  3. 水管空档的下降,01背包

总结:
如果有单向性,先考虑一下dp,再去想爆搜

Code2

请先思考后再展开
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
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
//*******************全局常量*******************
const int MAXN=10001;
const int INF=0x3f3f3f3f;
//*******************全局定义*******************
int n,m,k;
int xx[MAXN],yy[MAXN];
int l[MAXN],r[MAXN];
//*******************实现*******************
int f[MAXN][1001];
void solve()
{
memset(f,63,sizeof(f));
for(int i=1;i<=m;i++) f[0][i]=0;
for(int x=1;x<=n;x++)
{
//1. up
for(int y=xx[x-1]+1;y<=m;y++) f[x][y]=mymin(f[x-1][y-xx[x-1]],f[x][y-xx[x-1]])+1;
//2. up-特判m
for(int k=m-xx[x-1];k<=m;k++) f[x][m]=mymin( f[x][m],mymin(f[x-1][k],f[x][k])+1 );
//3. lock
for(int y=1;y<=l[x];y++) f[x][y]=INF;
for(int y=r[x];y<=m;y++) f[x][y]=INF;
//4. down
for(int y=l[x]+1;y<=r[x]-1;y++)
if(y+yy[x-1]<=m) f[x][y]=mymin(f[x][y],f[x-1][y+yy[x-1]]);
}
}
//*******************主函数*******************
int pp[MAXN];
int main()
{
//freopen("tmp.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<=n-1;i++) scanf("%d%d",&xx[i],&yy[i]);
for(int i=0;i<=n;i++) l[i]=0,r[i]=m+1;
for(int i=1;i<=k;i++)
{
scanf("%d",&pp[i]);
scanf("%d%d",&l[ pp[i] ],&r[ pp[i] ]);
}
solve();
int ans=INF,cnt=k;
for(int x=n;x>=1;x--)
{
for(int y=l[x]+1;y<=r[x]-1;y++) ans=mymin(ans,f[x][y]);
if(ans!=INF) break;//成功
if(r[x]<=m) cnt--;//失败
}
if(cnt==k) printf("1\n%d",ans);
else printf("0\n%d",cnt);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/ad3d.html
转载请注明出处,谢谢!