惠州专业网站建设,wordpress 总页码数,闸北网站推广公司,专门做教育的视频网站#题目链接
[NOIP2014 提高组] 飞扬的小鸟
题目描述
Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度#xff0c;让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话#xff0c;便宣告失败…#题目链接
[NOIP2014 提高组] 飞扬的小鸟
题目描述
Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话便宣告失败。
为了简化问题我们对游戏规则进行了简化和改编:
游戏界面是一个长为 n n n高为 m m m 的二维平面其中有 k k k 个管道忽略管道的宽度。
小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发到达游戏界面最右边时游戏完成。
小鸟每个单位时间沿横坐标方向右移的距离为 1 1 1竖直移动的距离由玩家控制。如果点击屏幕小鸟就会上升一定高度 x x x每个单位时间可以点击多次效果叠加如果不点击屏幕小鸟就会下降一定高度 y y y。小鸟位于横坐标方向不同位置时上升的高度 x x x 和下降的高度 y y y 可能互不相同。
小鸟高度等于 0 0 0 或者小鸟碰到管道时游戏失败。小鸟高度为 m m m 时无法再上升。
现在,请你判断是否可以完成游戏。如果可以输出最少点击屏幕数否则输出小鸟最多可以通过多少个管道缝隙。
输入格式
第 1 1 1 行有 3 3 3 个整数 n , m , k n, m, k n,m,k分别表示游戏界面的长度高度和水管的数量每两个整数之间用一个空格隔开
接下来的 n n n 行每行 2 2 2 个用一个空格隔开的整数 x x x 和 y y y依次表示在横坐标位置 0 ∼ n − 1 0 \sim n-1 0∼n−1 上玩家点击屏幕后小鸟在下一位置上升的高度 x x x以及在这个位置上玩家不点击屏幕时小鸟在下一位置下降的高度 y y y。
接下来 k k k 行每行 3 3 3 个整数 p , l , h p,l,h p,l,h每两个整数之间用一个空格隔开。每行表示一个管道其中 p p p 表示管道的横坐标 l l l 表示此管道缝隙的下边沿高度 h h h 表示管道缝隙上边沿的高度输入数据保证 p p p 各不相同但不保证按照大小顺序给出。
输出格式
共两行。
第一行包含一个整数如果可以成功完成游戏则输出 1 1 1否则输出 0 0 0。
第二行包含一个整数如果第一行为 1 1 1则输出成功完成游戏需要最少点击屏幕数否则输出小鸟最多可以通过多少个管道缝隙。
样例 #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
样例输入 #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 % 30\% 30% 的数据 5 ≤ n ≤ 10 , 5 ≤ m ≤ 10 , k 0 5 \leq n \leq 10, 5 \leq m \leq 10, k0 5≤n≤10,5≤m≤10,k0保证存在一组最优解使得同一单位时间最多点击屏幕 3 3 3 次
对于 50 % 50\% 50% 的数据 5 ≤ n ≤ 20 , 5 ≤ m ≤ 10 5 \leq n \leq 20, 5 \leq m \leq 10 5≤n≤20,5≤m≤10保证存在一组最优解使得同一单位时间最多点击屏幕 3 3 3 次
对于 70 % 70\% 70% 的数据 5 ≤ n ≤ 1000 , 5 ≤ m ≤ 100 5 \leq n \leq 1000, 5 \leq m \leq 100 5≤n≤1000,5≤m≤100
对于 100 % 100\% 100% 的数据 5 ≤ n ≤ 10000 5 \leq n \leq 10000 5≤n≤10000 5 ≤ m ≤ 1000 5 \leq m \leq 1000 5≤m≤1000 0 ≤ k n 0 \leq k n 0≤kn 0 x , y m 0 x,y m 0x,ym 0 p n 0 p n 0pn 0 ≤ l h ≤ m 0 \leq l h \leq m 0≤lh≤m l 1 h l 1 h l1h。
算法思想
根据题目描述在每一个单位时间内有多种选择。如果把每个单位时间内点击屏幕看成一个阶段可以有下面若干种情况
可以选择点击 0 0 0次下降 y y y点击 1 1 1次上升 x x x点击 2 2 2次上升 2 × x 2\times x 2×x…点击 k k k次上升 k × x k\times x k×x
该问题属于有限制的选择优化问题因此可以采用类似完全背包的思想进行处理。
状态表示 f [ i ] [ j ] f[i][j] f[i][j]表示沿横坐标方向右移 i i i个单位、并且飞行高度为 j j j时需要最少点击屏幕数。
状态计算
从最后一步分析要计算 f [ i ] [ j ] f[i][j] f[i][j]可以根据上一阶段也就是在第 i − 1 i-1 i−1个单位时间的选择分成下面若干种情况
在第 i − 1 i-1 i−1个单位时间不点击屏幕飞到横坐标 i i i时高度会下降 y y y才能到达 j j j此时最少点击屏幕数为 f [ i − 1 ] [ j y ] f[i-1][jy] f[i−1][jy]其中 j y ≤ m jy\le m jy≤m在第 i − 1 i-1 i−1个单位时间点击 1 1 1次屏幕飞到横坐标 i i i时高度会上升 x x x才能到达 j j j此时最少点击屏幕数为 f [ i − 1 ] [ j − x ] 1 f[i-1][j-x]1 f[i−1][j−x]1在第 i − 1 i-1 i−1个单位时间点击 2 2 2次屏幕飞到横坐标 i i i时高度会上升 2 × x 2\times x 2×x才能到达 j j j此时最少点击屏幕数为 f [ i − 1 ] [ j − 2 × x ] 2 f[i-1][j-2\times x]2 f[i−1][j−2×x]2…在第 i − 1 i-1 i−1个单位时间点击 k k k次屏幕飞到横坐标 i i i时高度会上升 k × x k\times x k×x才能到达 j j j此时最少点击屏幕数为 f [ i − 1 ] [ j − k × x ] k f[i-1][j-k\times x]k f[i−1][j−k×x]k其中 j − k × x 0 j-k\times x \gt 0 j−k×x0
因此 f [ i ] [ j ] m i n { f [ i − 1 ] [ j y ] , f [ i − 1 ] [ j − x ] 1 , f [ i − 1 ] [ j − 2 × x ] 2 , . . . , f [ i − 1 ] [ j − k × x ] k } f[i][j]min\{f[i-1][jy], f[i-1][j-x]1, f[i-1][j-2\times x]2,...,f[i-1][j-k\times x]k\} f[i][j]min{f[i−1][jy],f[i−1][j−x]1,f[i−1][j−2×x]2,...,f[i−1][j−k×x]k}。
初始状态
求点击次数的最小值 f [ i ] [ j ] f[i][j] f[i][j]应初始化为无穷大小鸟从游戏界面最左边任意整数高度位置出发因此 f [ 0 ] [ j ] 0 f[0][j] 0 f[0][j]0其中 0 j ≤ m 0\lt j\le m 0j≤m。
边界情况
在计算状态的过程中需要处理下面的边界情况
小鸟高度等于 0 0 0 或者小鸟碰到管道时游戏失败 因此枚举高度 j j j时应保证 j 0 j\gt 0 j0并且 l j h l\lt j\lt h ljh l l l 表示此管道缝隙的下边沿高度 h h h 表示管道缝隙上边沿的高度。 小鸟高度为 m m m 时无法再上升 意味着状态 f [ i ] [ m ] f[i][m] f[i][m]可以由 i − 1 i-1 i−1阶段的任意状态转移过来。例如当高度为 j j j时到 m m m的距离是 m − j m-j m−j每次点击屏幕上升 x x x那么需要点击 ⌈ m − j x ⌉ \lceil \frac{m-j}{x}\rceil ⌈xm−j⌉次。因此 f [ i ] [ m ] m i n { f [ i ] [ m ] , f [ i − 1 ] [ j ] ⌈ m − j x ⌉ } f[i][m]min\{f[i][m], f[i-1][j] \lceil \frac{m-j}{x}\rceil\} f[i][m]min{f[i][m],f[i−1][j]⌈xm−j⌉}其中 1 ≤ j m 1\le j\lt m 1≤jm。除此之外在 i − 1 i-1 i−1阶段高度为 m m m时点击 1 1 1次屏幕也可以转移到 f [ i ] [ m ] f[i][m] f[i][m]因此 f [ i ] [ m ] m i n { f [ i ] [ m ] , f [ i − 1 ] [ m ] 1 } f[i][m]min\{f[i][m], f[i-1][m] 1\} f[i][m]min{f[i][m],f[i−1][m]1} 时间复杂度
状态数 n × m n\times m n×m在状态计算过程中需要枚举点击屏幕次数 k k k k ≤ m k\le m k≤m
因此时间复杂度为 O ( n m 2 ) 10000 × 100 0 2 1 0 10 O(nm^2)10000\times 1000^210^{10} O(nm2)10000×100021010只能拿到 85 85 85分。
代码实现85分
#include iostream
#include cstring
using namespace std;
const int N 10010, M 1010, INF 0x3f3f3f3f;
int f[N][M], x[N], y[N], L[N], H[N];
int main()
{int n, m, k;scanf(%d%d%d, n, m, k);for(int i 1; i n; i ) scanf(%d%d, x[i], y[i]);for(int i 1; i k; i ){int p, l, h;scanf(%d%d%d, p, l, h);L[p] l, H[p] h;}//初始状态memset(f, 0x3f, sizeof f);for(int j 1; j m; j ) f[0][j] 0;//状态计算枚举横坐标for(int i 1; i n; i ){//枚举高度for(int j 1; j m; j ){//没有管道飞行的高度在两根管道之间if(H[i] 0 || j L[i] j H[i]){//点击k次屏幕飞到(i,j)时for(int k 1; k * x[i] j; k )f[i][j] min(f[i][j], f[i - 1][j - k * x[i]] k);//不点击屏幕if(j y[i] m) f[i][j] min(f[i][j], f[i - 1][j y[i]]);} }//f[i][m]可以由i-1阶段的任意状态转移过来if(H[i] 0) //没有管道{//当i-1阶段在最高处时再点击1下也能转移到f[i][m]f[i][m] min(f[i][m], f[i - 1][m] 1); //计算其它高度走到最高处的点击次数距离(m-j)除以(上升高度x)向上取整for(int j 1; j m; j ){f[i][m] min(f[i][m], f[i - 1][j] (m - j x[i] - 1) / x[i]);}}}int ans INF;for(int j 1; j m; j ) ans min(ans, f[n][j]);//能够到达终点if(ans INF) printf(1\n%d, ans);else //不能到达终点{//从后向前找到最后能到达的位置for(int i n; i 0; i --)for(int j 1; j m; j ){if(f[i][j] INF) //能够到达该位置{int cnt 0; //统计管道数量注意从横坐标为0开始统计for(int k 0; k i; k ){if(H[k] ! 0) //有管道cnt ;}printf(0\n%d, cnt);return 0;}}}
}优化思想
依据状态计算方法 f [ i ] [ j ] m i n { f [ i − 1 ] [ j y ] , f [ i − 1 ] [ j − x ] 1 , f [ i − 1 ] [ j − 2 × x ] 2 , . . . , f [ i − 1 ] [ j − k × x ] k } f[i][j]min\{f[i-1][jy], f[i-1][j-x]1, f[i-1][j-2\times x]2,...,f[i-1][j-k\times x]k\} f[i][j]min{f[i−1][jy],f[i−1][j−x]1,f[i−1][j−2×x]2,...,f[i−1][j−k×x]k}需要枚举 k k k计算 m i n { f [ i − 1 ] [ j − x ] 1 , f [ i − 1 ] [ j − 2 × x ] 2 , . . . , f [ i − 1 ] [ j − k × x ] k } min\{f[i-1][j-x]1, f[i-1][j-2\times x]2,...,f[i-1][j-k\times x]k\} min{f[i−1][j−x]1,f[i−1][j−2×x]2,...,f[i−1][j−k×x]k}尝试利用空间换时间将计算的中间结果保存下来。
不妨设 g [ i ] [ j ] m i n { f [ i − 1 ] [ j − x ] 1 , f [ i − 1 ] [ j − 2 × x ] 2 , . . . , f [ i − 1 ] [ j − k × x ] k } g[i][j]min\{f[i-1][j-x]1, f[i-1][j-2\times x]2,...,f[i-1][j-k\times x]k\} g[i][j]min{f[i−1][j−x]1,f[i−1][j−2×x]2,...,f[i−1][j−k×x]k} 而 g [ i ] [ j − x ] m i n { f [ i − 1 ] [ j − 2 × x ] 1 , . . . , f [ i − 1 ] [ j − k × x ] k } g[i][j-x]min\{f[i-1][j-2\times x]1,...,f[i-1][j-k\times x]k\} g[i][j−x]min{f[i−1][j−2×x]1,...,f[i−1][j−k×x]k} 可得 g [ i ] [ j ] m i n { f [ i − 1 ] [ j − x ] 1 , g [ i ] [ j − x ] 1 } g[i][j]min\{f[i-1][j-x]1,g[i][j-x]1\} g[i][j]min{f[i−1][j−x]1,g[i][j−x]1} 那么 f [ i ] [ j ] m i n { f [ i − 1 ] [ j y ] , g [ i ] [ j ] } f[i][j]min\{f[i-1][jy], g[i][j]\} f[i][j]min{f[i−1][jy],g[i][j]}也就是说计算 f [ i ] [ j ] f[i][j] f[i][j]不再需要枚举 k k k。
时间复杂度
状态数 n × m n\times m n×m在状态计算的时间复杂度为 O ( 1 ) O(1) O(1)
因此时间复杂度为 O ( n m ) 10000 × 1000 1 0 7 O(nm)10000\times 100010^{7} O(nm)10000×1000107。
代码实现100分
#include iostream
#include cstring
using namespace std;
const int N 10010, M 1010, INF 0x3f3f3f3f;
int f[N][M], x[N], y[N], L[N], H[N], g[N][M];
int main()
{int n, m, k;scanf(%d%d%d, n, m, k);for(int i 1; i n; i ) scanf(%d%d, x[i], y[i]);for(int i 1; i k; i ){int p, l, h;scanf(%d%d%d, p, l, h);L[p] l, H[p] h;}//初始状态memset(f, 0x3f, sizeof f);memset(g, 0x3f, sizeof g);for(int j 1; j m; j ) f[0][j] 0;//状态计算枚举横坐标for(int i 1; i n; i ){//枚举高度for(int j 1; j m; j ){//处理g数组if(j x[i]) g[i][j] min(f[i - 1][j - x[i]] 1, g[i][j - x[i]] 1);//没有管道飞行的高度在两根管道之间if(H[i] 0 || j L[i] j H[i]){//优化后f[i][j]min(f[i-1][jy], g[i][j])f[i][j] g[i][j];//不点击屏幕if(j y[i] m) f[i][j] min(f[i][j], f[i - 1][j y[i]]);} }//f[i][m]可以由i-1阶段的任意状态转移过来if(H[i] 0) //没有管道{//当i-1阶段在最高处时再点击1下也能转移到f[i][m]f[i][m] min(f[i][m], f[i - 1][m] 1); //计算其它高度走到最高处的点击次数距离(m-j)除以(上升高度x)向上取整for(int j 1; j m; j ){f[i][m] min(f[i][m], f[i - 1][j] (m - j x[i] - 1) / x[i]);}}}int ans INF;for(int j 1; j m; j ) ans min(ans, f[n][j]);//能够到达终点if(ans INF) printf(1\n%d, ans);else //不能到达终点{//从后向前找到最后能到达的位置for(int i n; i 0; i --)for(int j 1; j m; j ){if(f[i][j] INF) //能够到达该位置{int cnt 0; //统计管道数量注意从横坐标为0开始统计for(int k 0; k i; k ){if(H[k] ! 0) //有管道cnt ;}printf(0\n%d, cnt);return 0;}}}
}
