NOIP2014 招展的小鸟题解

描述

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

NOIP2014 招展的小鸟题解

为了简化问题，我们对游戏规则进行了简化和改编：

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

现在，请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

格式

输入格式

第 1 行有 3 个整数 n，m，k，分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开；

接下来的 n 行，每行 2 个用一个空格隔开的整数 X 和 Y，依次表示在横坐标位置 0~n-1 上玩家点击屏幕后，小鸟在下一位置上升的高度 X，以及在这个位置上玩家不点击屏幕时，小鸟在下一位置下降的高度 Y。

接下来 k 行，每行 3 个整数 P，L，H，每两个整数之间用一个空格隔开。每行表示一个管道，其中 P 表示管道的横坐标，L 表示此管道缝隙的下边沿高度为 L，H 表示管道缝隙上边沿的高度（输入数据保证 P 各不相同，但不保证按照大小顺序给出）。

输出格式

共两行。

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

样例1

样例输入1[复制]

样例输出1[复制]

1
6

样例2

样例输入2[复制]

样例输出2[复制]

0
3

限制

对于 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。

提示

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

NOIP2014 招展的小鸟题解

“请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。”

将解结构表示为ϕ=(b,h,t)，b为1或0表示是否可以完成游戏，若可以，h表示最少点击屏幕数；否则，t表示最多可以通过多少个管道缝隙。定义ϕ1=(b1,h1,t1)<ϕ2=(b2,h2,t2)当且仅当(b1=0,b2=1)或(b1=b2=0,t1<t2)或(b1=b2=1,h1>h2)，则我们可以对解的表示创建全序关系，而可行解的最大值为最优解，我们可以用有符号数来优化其内存表示。

定义ϕ+t′={(b,h,t+t′)(b,h,t)b=0b=1，ϕ+h′={(b,h,t)(b,h+h′,t)b=0b=1

设ϕ(x,y)为从(x,y)坐标开始游戏的最优解，α(x)和β(x)分别表示上升与下降的高度，t(x)表示横坐标处是否存在管道，则对于不存在管道的平面区域

ϕ (x, y) = max h = 0, 1, 2, . . . {ϕ (x + 1, y + h * α (x)) + h + t (x) ϕ (x + 1, y - β (x)) + t (x) h > 0 h = 0

而所求解为max1≤y≤m{ϕ(0,y)}。观察到表达式具有最优子结构性质，因此可以使用动态规划进行求解，时间复杂度为O(n∗m2)。

我们可以将每次可以不点击或点击多次，变为每次可以不点击、点击h0次或原地上升一次，其中h0为点击进入下一横坐标非管道区域的最小次数。从而可以进行下述优化，设ϕ(x,y,γ)表示(x,y)坐标开始游戏的最优解，γ=0表示第一步不能为原地上升，而γ=1表示第一步可以为原地上升，则

ϕ (x, y, 0) = max {ϕ (x + 1, y + h 0 * α (x), 1) + h (1) + t (x) ϕ (x + 1, y - β (x), 0) + t (x)

ϕ (x, y, 1) = max ⎧ ⎩ ⎨ ⎪ ⎪ ϕ (x + 1, y + h 0 * α (x), 1) + h (1) + t (x) ϕ (x + 1, y - β (x), 0) + t (x) ϕ (x, y + α (x - 1), 1) + h (1) + t (x) x \neq 0

从而得到O(n∗m)的算法，空间复杂度可以实现为O(n+m)。

也可这样理解：本体类似于经典的完全背包问题，每个阶段解决向上或者向下，而且次数不限，类似于物品个数没有限制。所以f[i][j]的状态可以从f[i-1][*]和f[i][*]中转移过来。

保证时间复杂度是O（nm）即可。

就是flybird那个游戏，不能碰管道，在每个位置上点击和不点击都有不同的上升下降高度，求从左面飞到右面的最小点击数（可以在一个位置点击多次）。
【算法描述】
动态规划。整张地图就是一个表
f[i, j]表示到(i, j)位置的最小点击数。
f[i, j] = min(f[i, j], f[x, j - 1] + 1) 点击
f[i - drop[j - 1], j - 1] 不点击
注意：在顶端需要判断是不是点多下超出了范围要回到顶端。
For j :=1 To n DO
For i :=m - 1 DownTo 0 DO Begin
If not flag[i, j] Then continue;

If i = 0 Then Begin
For k :=0 To m - 1 Do
If flag[i + k, j - 1] Then Begin
If k = 0 Then x := 1;
If k > 0 Then
IF k mod up[j - 1] = 0 Then x := k Div up[j - 1]
Else x := k Div up[j - 1] + 1;
f[i, j] := min(f[i, j], f[i + k, j - 1] + x);
End;
End Else Begin
x := i + up[j - 1];
If x < m Then Begin
If flag[x, j] Then
f[i, j] := min(f[i, j], f[x, j] + 1);
If flag[x, j - 1] Then
f[i, j] := min(f[i, j], f[x, j - 1] + 1);
End;
x := i - drop[j - 1];
If x >= 0 Then
If flag[x, j - 1] Then f[i, j] := min(f[i, j], f[x, j - 1]);
End;
End;

不难发现这样做肯定会超时。不难发现有很多的子问题重叠，需要做优化。
每次做一个点就要看前一列下面的那些点，有些点是被重复扫过的，显然没有意义。

For j :=1 To n DO Begin
For i :=m DownTo 1 DO Begin
If i <= m - up[j - 1] Then Begin
x1 := i + up[j - 1];
If x1 <= m Then Begin
f[i, j] := min(f[i, j], f[x1, j - 1] + 1);
f[i, j] := min(f[i, j], f[x1, j] + 1);
End;
End;
If i = 1 Then Begin
If i + up[j - 1] <= m Then
For k :=i + up[j - 1] Downto 1 Do Begin

f[i, j] := min(f[i, j], f[k, j - 1] + 1);
f[i, j] := min(f[i, j], f[k, j] + 1);
End;
End;
End;
For i :=y[j] + 1 To x[j] - 1 DO Begin
If i - drop[j - 1] > 0 Then
f[i, j] := min(f[i, j], f[i - drop[j - 1], j - 1]);
End;

【程序】
Program bird;
Const
infile = 'bird15.in';
outfile = 'bird.out';
Var
i1, max1, n, m, p, i,j,k,x1,y1,z,xx,xxx,Ans:longint;
ff : Boolean;
f : Array[0..2000, 0..10100] of longint;
flag : Array[0..2000, 0..11000] of Boolean;
x, y, b, up, drop : Array[0..10000] of longint;
Function min(x, y : longint) : longint;
Begin
If x < y Then exit(x) Else exit(y);
End;
Begin
{Assign(input, '???');
Assign(output, '???');
Reset(input);
Rewrite(output);}
Readln(n, m, p);
For i :=0 To n - 1 DO Readln(up[i], drop[i]);
Fillchar(flag, sizeof(flag), true);
For i :=1 To n DO Begin
y[i] := 0;
x[i] := m + 1;
End;
For i :=1 To p Do Begin
Readln(b[i], x1, y1);
x[b[i]] := x1;
y[b[i]] := y1;
x[b[i]] := m - x[b[i]] + 1;
y[b[i]] := m - y[b[i]] + 1;
End;
For i :=0 To m Do
For j :=0 TO n Do
f[i, j] := maxlongint - 10000;
For i :=1 TO m Do f[i, 0] := 0;
For j :=1 To n DO Begin
For i :=m DownTo 1 DO Begin
If i <= m - up[j - 1] Then Begin
x1 := i + up[j - 1];
If x1 <= m Then Begin
f[i, j] := min(f[i, j], f[x1, j - 1] + 1);
f[i, j] := min(f[i, j], f[x1, j] + 1);
End;
End;
If i = 1 Then Begin
If i + up[j - 1] <= m Then
For k :=i + up[j - 1] Downto 1 Do Begin

f[i, j] := min(f[i, j], f[k, j - 1] + 1);
f[i, j] := min(f[i, j], f[k, j] + 1);
End;
End;
End;
For i :=y[j] + 1 To x[j] - 1 DO Begin
If i - drop[j - 1] > 0 Then
f[i, j] := min(f[i, j], f[i - drop[j - 1], j - 1]);
End;

For i :=0 To y[j] Do Begin
// Writeln(i, ' ', j);
f[i, j] := maxlongint - 10000;
ENd;
For i :=x[j] To m DO BEgin
// Writeln(i, j);
f[i, j] := maxlongint - 10000;
ENd;
End;
{ For i :=1 TO m DO Begin
For j :=0 TO n Do Write(f[i, j]:11);
Writeln;
End;}
Ans := maxlongint - 10000;
For i :=1 TO m DO Begin
If flag[i, n] Then
If f[i, n] < Ans Then Begin
Ans := f[i, n];
// Writeln(i, ' ', Ans);
End;
End;
IF Ans = maxlongint - 10000 Then Writeln(0) Else Begin
Writeln(1);
Writeln(Ans);
End;
IF Ans = maxlongint - 10000 Then Begin
max1 := 0;
For i1 :=1 To p Do Begin
ff := true;
For i :=1 To m DO
If f[i, b[i1]] < maxlongint - 10000 Then Begin
Inc(max1);
ff := false;
Break;
End;
// If ff Then Writeln(b[i1]);
// If ff Then Break;
End;
Writeln(max1);
End;
{Close(input);
Close(output);}
End.

NOIP2014 招展的小鸟 题解

描述

格式

输入格式

输出格式

样例1

样例输入1[复制]

样例输出1[复制]

样例2

样例输入2[复制]

样例输出2[复制]

限制

提示

相关推荐