本文主要是介绍解题报告（1）——飞扬的小鸟，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
飞扬的小鸟【NOIP2014提高组】
题目背景
NOIP2014提高组 Day1试题。
题目描述
Flappy Bird是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。
为了简化问题，我们对游戏规则进行了简化和改编：
1．游戏界面是一个长为 n，高为 m 的二维平面，其中有k个管道（忽略管道的宽度）。
2．小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。
3．小鸟每个单位时间沿横坐标方向右移的距离为 1，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 X，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 Y。小鸟位于横坐标方向不同位置时，上升的高度 X 和下降的高度 Y可能互不相同。
4．小鸟高度等于 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
输入
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
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
输出
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。
算法分析：
方法一：直接模拟+动归 预计得分：70；
1）f[i][j]表示在横坐标为i，纵坐标为j时，最小的跳跃次数。（因担心MLE，所以实际代码由滚动数组处理），初始化f[0][j]全部为零。
2）依次枚举每个横纵坐标，，判断其是否在上轮可以到达，再依次将本轮可到达的位置标注记录。（注意不要超过上下限）
3）若有管道进行判断是否在可行范围内。
4）每轮纵坐标循环后，将未更新的点标注为-1（不可到达），方便下轮判断。
5）若检测到某轮结束全部点位为-1，输出0，计算已过管道并输出，结束程序。
6）最后一轮成功进行完毕，比较f[n][j]，得到不等于-1，且最小的一个，输出1，输出最小值，结束程序。
#include#include#include#include#includeusing namespace std; int n,m,k,po,j1,j2,mi,sum,pic; /*n:横坐标;m:纵坐标;k:管道数; po:临时位置记录; j1,j2:滚动数组推到用*/ /*mi:记录最小跳跃次数;sum:记录本轮无法到达的点位个数;pic:记录已通过管道数*/ int up[10001],down[10001]; /*up[i]:若i-1时点击屏幕，i时的上升高度*/ /*down[i]:若i-1时不点击屏幕，i时的下降高度*/ int pid[10001],piu[10001]; /*pid[i]:i处管道下方的最高点*/ /*piu[i]:i处管道上方的最低点*/ int f[2][10001]; /*滚动数组，记录当前行和上一行的最优解*/ inline void R(int &v)/*读入优化*/ { v=0; char c=0; bool p=true; while(c>'9'||c<'0') { if(c=='-') { p=false; } c=cin.get(); } while(c<='9'&&c>='0') { v=(v<<3)+(v<<1)+c-'0'; c=cin.get(); } if(p==false) { v=-v; } } int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); /*cin解绑*/ R(n); R(m); R(k); for(int i=1;i<=n;++i) { R(up[i]); R(down[i]); } for(int i=1;i<=k;++i) { R(po); R(pid[po]); R(piu[po]); } for(int i=1;i<=m;++i) /*初始化为0*/ { f[0][i]=0; } j1=0; j2=1; /*滚动数组的坐标初始化*/ for(int i=1;i<=n;++i) /*枚举横坐标*/ { if(piu[i]>0) /*若当前列存在管道*/ { pic++; /*管道计数加1*/ } j1=(j1+1)%2; /*改变滚动数组坐标*/ j2=(j2+1)%2; /*改变滚动数组坐标*/ memset(f[j1],127,sizeof(f[j1])); /*初始化当前行最优解*/ for(int j=1;j<=m;++j) /*枚举纵坐标*/ { if(f[j2][j]!=-1) /*若上轮判定可以到达*/ { int q=j; int cnt=0; while(q<=m) /*判断点击次数和可以到达的位置*/ { q=q+up[i]; cnt++; /*点击次数*/ if(piu[i]!=0) /*若存在管道*/ { if(q pid[i]) /*保证在可以停留的范围*/ { f[j1][q]=min(f[j2][j]+cnt,f[j1][q]);/*更新最优解*/ } else { if(q>=piu[i]) /*若已经大于高处管道的最低点*/ { break; /*跳出循环*/ } } } else { if(q>m) { f[j1][m]=min(f[j2][j]+cnt,f[j1][m]); /*若超过高线，则停留在高线*/ } else { f[j1][q]=min(f[j2][j]+cnt,f[j1][q]); /*若未超过，更新当前位置*/ } } } q=j; cnt=0; /*清零计数*/ q=q-down[i]; /*判断若直接下降*/ if(piu[i]!=0) /*若有管道*/ { if(q pid[i]) /*判断是否满足条件*/ { f[j1][q]=min(f[j2][j],f[j1][q]); /*更新*/ } } else { if(q>0) /*若未到地面*/ { f[j1][q]=min(f[j2][j],f[j1][q]);/*更新*/ } } } } // cout< <
方法二：动归+优化 预计得分：100；
1）f[i][j]表示在横坐标为i，纵坐标为j时，最小的跳跃次数。（因担心MLE，所以实际代码由滚动数组处理），初始化f[0][j]全部为零。
2）依次枚举每个纵坐标，，判断其是否在本轮可以到达，方法：判断j-up[i]本轮和上轮是否有有效值。（注意不要超过上下限）
3）单独判断m-up[i]到m之间，本轮和上轮的可用值中的最小值。
4）最后将有管道的地方标注为不可行。
5）每轮纵坐标循环后，将未更新的点标注为-1（不可到达），方便下轮判断。
6）若检测到某轮结束全部点位为-1，输出0，计算已过管道并输出，结束程序。
7）最后一轮成功进行完毕，比较f[n][j]，得到不等于-1，且最小的一个，输出1，输出最小值，结束程序。
Source ：
Source ：
#include#include#include#include#includeusing namespace std; int n,m,k,po,j1,j2,mi,sum,pic; /*n:横坐标;m:纵坐标;k:管道数; po:临时位置记录; j1,j2:滚动数组推到用*/ /*mi:记录最小跳跃次数;sum:记录本轮无法到达的点位个数;pic:记录已通过管道数*/ int up[10001],down[10001]; /*up[i]:若i-1时点击屏幕，i时的上升高度*/ /*down[i]:若i-1时不点击屏幕，i时的下降高度*/ int pid[10001],piu[10001]; /*pid[i]:i处管道下方的最高点*/ /*piu[i]:i处管道上方的最低点*/ int f[2][10001]; /*滚动数组，记录当前行和上一行的最优解*/ inline void R(int &v) /*读入优化*/ { v=0; char c=0; bool p=true; while(c>'9'||c<'0') { if(c=='-') { p=false; } c=cin.get(); } while(c<='9'&&c>='0') { v=(v<<3)+(v<<1)+c-'0'; c=cin.get(); } if(p==false) { v=-v; } } int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); /*cin解绑*/ R(n); R(m); R(k); for(int i=1;i<=n;++i) { R(up[i]); R(down[i]); } for(int i=1;i<=k;++i) { R(po); R(pid[po]); R(piu[po]); } for(int i=1;i<=m;++i) /*初始化为0*/ { f[0][i]=0; } j1=0; j2=1; /*滚动数组的坐标初始化*/ for(int i=1;i<=n;++i) /*枚举横坐标*/ { if(piu[i]>0) /*若当前列存在管道*/ { pic++; /*管道计数加1*/ } j1=(j1+1)%2; /*改变滚动数组坐标*/ j2=(j2+1)%2; /*改变滚动数组坐标*/ memset(f[j1],127,sizeof(f[j1])); /*初始化当前行最优解*/ for(int j=1+up[i];j<=m;++j) /*枚举当前列跳跃高度以上的点*/ { if(j!=m) { if(f[j2][j-up[i]]!=-1) /*判断上次起点能否达到*/ { f[j1][j]=min(f[j1][j],f[j2][j-up[i]]+1); /*更新最优解*/ } if(f[j1][j-up[i]]!=f[j1][0]) /*本轮之前位置可以到达*/ { f[j1][j]=min(f[j1][j],f[j1][j-up[i]]+1); /*更新最优解*/ } } else { for(k=m-up[i];k<=m;++k) /*单独处理最顶点*/ { if(f[j2][k]!=-1) /*若上轮位置可用*/ { f[j1][m]=min(f[j2][k]+1,f[j1][m]); /*更新最优解*/ } if(f[j1][k]!=f[j1][0]) /*本轮有位置可用*/ { f[j1][m]=min(f[j1][k]+1,f[j1][m]); /*更新最优解*/ } } } } for(int j=1;j<=m-down[i];++j) /*枚举向下落点*/ { if(f[j2][j+down[i]]!=-1) /*若上轮位置可用*/ { f[j1][j]=min(f[j1][j],f[j2][j+down[i]]); /*更新最优解*/ } } if(piu[i]>0) /*最后判断管道*/ { for(int k=1;k<=pid[i];++k) /*处理下方管道*/ { f[j1][k]=-1; sum++; } for(int k=piu[i];k<=m;++k) /*处理上方管道*/ { f[j1][k]=-1; sum++; } } for(int j=1;j<=m;++j) /*处理不能到达的位置*/ { if(f[j1][j]==f[j1][0]) { f[j1][j]=-1; sum++; /*计数*/ } } if(sum==m) /*全部不能到达*/ { cout<<"0"<
Summary：
动态规划不像一般算法存在着使用的模板，每道题都有其不同的特点，只有认真揣摩分析每一道题的本质，再辅以所知道的算法，找到规划的方向才能够正确完成。当然，在考试中如果实在没有找到规划方向，就可以尝试用搜索或暴力模拟等极端方法，尽量得分。
这篇关于解题报告（1）——飞扬的小鸟的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
![[SWPUCTF 2021 新生赛]web方向(一到六题) 解题思路，实操解析，解题软件使用，解题方法教程](https://i-blog.csdnimg.cn/direct/bcfaab8e5a68426b8abfa71b5124a20d.png)
