提示
如下图所示，蓝色直线表示小鸟的飞行轨迹，红色直线表示管道。
“请你判断是否可以完成游戏。如果可以，，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。”
将解结构表示为)，则我们可以对解的表示创建全序关系，而可行解的最大值为最优解，我们可以用有符号数来优化其内存表示。
定义
设为从(x,y)坐标开始游戏的最优解，分别表示上升与下降的高度，t(x)表示横坐标处是否存在管道，则对于不存在管道的平面区域
而所求解为。
我们可以将每次可以不点击或点击多次，变为每次可以不点击、点击表示第一步可以为原地上升，则
从而得到。
也可这样理解：本体类似于经典的完全背包问题，每个阶段解决向上或者向下，而且次数不限，类似于物品个数没有限制。所以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.
它不同于旅游，那需要一个风景稍微漂亮的地方，
