网站大致内容,深圳开发公司,上海网站建设最佳方案,企业网站建设方案流程P1941 飞扬的小鸟
Description
Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度#xff0c;让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话#xff0c;便宣告失败。
为了简化问题让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话便宣告失败。
为了简化问题我们对游戏规则进行了简化和改编:
游戏界面是一个长为 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 时无法再上升。
现在,请你判断是否可以完成游戏。如果可以输出最少点击屏幕数否则输出小鸟最多可以通过多少个管道缝隙。
Input
第 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 各不相同但不保证按照大小顺序给出。
Output
共两行。
第一行包含一个整数如果可以成功完成游戏则输出 1 1 1否则输出 0 0 0。
第二行包含一个整数如果第一行为 1 1 1则输出成功完成游戏需要最少点击屏幕数否则输出小鸟最多可以通过多少个管道缝隙。
Sample #1
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 3Sample Output #1
1
6Sample #2
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 10Sample Output #2
0
3Hint
如下图所示蓝色直线表示小鸟的飞行轨迹红色直线表示管道。 Constraints
对于 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。 Solution
对于此题分为 2 2 2 种情况
对于位置 i i i 不按上升键此时会下降 y i y_i yi对于位置 i i i 按 k k k 次上升键此时会上升 k ⋅ x i k\cdot x_i k⋅xi
故可以由 01 01 01 背包 与 完全背包 融合来解决。
考虑设计状态 f i , j f_{i,j} fi,j 表示在第 i i i 个位置高度为 j j j 的最小操作次数 70 p t s \mathrm{70\ pts} 70 pts 做法
转移分为两种情况如下 f i , j { f i − 1 , j y i j y i ≤ m f i − 1 , j − k ⋅ x i k j − k ⋅ x i ≥ 1 f_{i,j}\begin{cases} f_{i - 1, jy_i} jy_i\le m \\ f_{i - 1, j - k\cdot x_i}k j - k\cdot x_i \ge 1 \end{cases} fi,j{fi−1,jyifi−1,j−k⋅xikjyi≤mj−k⋅xi≥1 若在 i i i 位置一次不按则从 i − 1 i -1 i−1 位置到 i i i 位置会下降 y i y_i yi 个单位对应着 i − 1 i-1 i−1 位置的高度比当前会高 y i y_i yi 个单位。
若在 j j j 位置按 k k k 次则从 i − 1 i-1 i−1 位置到 i i i 位置会上升 k ⋅ x i k\cdot x_i k⋅xi 个单位对应着 i − 1 i-1 i−1 位置的高度比当前高度会低 k ⋅ x i k\cdot x_i k⋅xi 个高度。
时间复杂度 O ( n m 2 ) O(nm^2) O(nm2) 100 p t s \mathrm{100pts} 100pts 做法
对于上述式子采取与完全背包优化方式类似的方法来优化
将式子展开 f i , j { f i − 1 , j y i f i − 1 , j − x i 1 , f i − 2 , j − 2 ⋅ x i 2 , f i − 3 , j − 3 ⋅ x i 3 , … f_{i,j}\begin{cases} f_{i - 1, jy_i} \\ f_{i - 1, j - x_i} 1, f_{i - 2, j - 2\cdot x_i} 2, f_{i - 3, j - 3\cdot x_i} 3,\dots \end{cases} fi,j{fi−1,jyifi−1,j−xi1,fi−2,j−2⋅xi2,fi−3,j−3⋅xi3,… 在观察 f i , j − x i f_{i,j-x_i} fi,j−xi 的式子 f i , j − x i { f i − 1 , j − x i y i f i − 2 , j − 2 ⋅ x i 1 , f i − 3 , j − 3 ⋅ x i 2 , … f_{i,j-x_i}\begin{cases} f_{i - 1, j-x_iy_i} \\ f_{i - 2, j - 2\cdot x_i} 1, f_{i - 3, j - 3\cdot x_i} 2,\dots \end{cases} fi,j−xi{fi−1,j−xiyifi−2,j−2⋅xi1,fi−3,j−3⋅xi2,… 此时我们会发现第 2 2 2 种情况的式子惊奇的相似只是少了一项 f i − 1 , j − x i f_{i-1,j-x_i} fi−1,j−xi且每一项都少了一个 1 1 1故考虑借用数组 g i , j g_{i,j} gi,j 表示 min ( f i − 1 , j − x i , f i − 1 , j − 2 ⋅ x i , … ) \min(f_{i-1,j-x_i},f_{i-1,j-2\cdot x_i, \dots}) min(fi−1,j−xi,fi−1,j−2⋅xi,…)
由上面可得出 g g g 数组的转移方程 g i , j min ( g i − 1 , j − x i 1 , f i − 1 , j − x i 1 ) g_{i,j}\min(g_{i-1,j-x_i}1,f_{i-1,j-x_i}1) gi,jmin(gi−1,j−xi1,fi−1,j−xi1) 含义就是用 f i , j − x i f_{i,j-x_i} fi,j−xi 的第 2 2 2 种情况 1 1 1再补上少了的一部分 f i − 1 , j − x i 1 f_{i-1,j-x_i}1 fi−1,j−xi1
这样对于 f i , j f_{i,j} fi,j 转移如下 f i , j min ( f i − 1 , j y i , g i , j ) f_{i,j}\min(f_{i-1,jy_i},g_{i,j}) fi,jmin(fi−1,jyi,gi,j)
时间复杂度 O ( n m ) O(nm) O(nm) 空间优化
由于观察发现 g g g 数组只用到了坐标 i i i所以这一维可以去掉 细节点播
对于 f i , m f_{i,m} fi,m 需要特殊处理因为 小鸟高度为 m m m 时无法再上升所以会停留在 m m m故这个位置可以有 i − 1 i-1 i−1 位置上的任何一个高度转移而来。
即 f i , m min ( f i − 1 , j ⌈ m − j x i ⌉ ) f_{i,m}\min(f_{i-1,j}\left\lceil \frac{m-j}{x_i} \right\rceil) fi,mmin(fi−1,j⌈xim−j⌉)
但是特别注意 j m jm jm 时而 ⌈ m − j x i ⌉ \left\lceil \frac{m-j}{x_i} \right\rceil ⌈xim−j⌉ 会是 0 0 0如果是 0 0 0 那么还是会掉下去的所以要特殊处理 j m jm jm 的情况 f i , m f i − 1 , m 1 f_{i,m}f_{i-1,m}1 fi,mfi−1,m1
或者是不特殊处理 f i , m min ( f i − 1 , j max ( 1 , ⌈ m − j x i ⌉ ) ) f_{i,m}\min(f_{i-1,j}\max(1,\left\lceil \frac{m-j}{x_i} \right\rceil)) fi,mmin(fi−1,jmax(1,⌈xim−j⌉)) A t t e n t i o n : \mathrm{Attention:} Attention: 只有当上面没有管道的时候才需要处理。 结果输出
枚举所有的 j j j取 f n , j f_{n,j} fn,j 的最小值。
如果无法到达则 i i i 总大到小枚举枚举 j j j 确定是否可以到达如果可以统计前方有多少个管子输出即可。 Code
#include iostream
#include cstring
#define int long longusing namespace std;typedef pairint, int PII;const int SIZE 1e4 10, INF 0x3f3f3f3f3f3f3f3f;int N, M, K;
int X[SIZE], Y[SIZE];
int L[SIZE], H[SIZE];
int F[SIZE][SIZE], G[SIZE];signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin N M K;for (int i 1; i N; i )cin X[i] Y[i];int Pos, l, h;while (K --){cin Pos l h;L[Pos] l, H[Pos] h;}memset(F, 0x3f, sizeof F);for (int i 1; i M; i )F[0][i] 0;for (int i 1; i N; i ){memset(G, 0x3f, sizeof G);for (int j 1; j M; j ){if (j X[i]) G[j] min(G[j - X[i]], F[i - 1][j - X[i]]) 1;if (!H[i] || j L[i] j H[i]){F[i][j] G[j];if (j Y[i] M) F[i][j] min(F[i][j], F[i - 1][j Y[i]]);}}if (!H[i])for (int j 1; j M; j )F[i][M] min(F[i][M], F[i - 1][j] max(1ll, (M - j X[i] - 1) / X[i]));}int Result INF;for (int j 1; j M; j )Result min(Result, F[N][j]);if (Result INF)cout 1 endl Result endl;else{cout 0 endl;for (int i N; i 0; i --){bool Flag false;for (int j 1; j M; j )if (F[i][j] INF){int Count 0;for (int k 0; k i; k )if (H[k])Count ;cout Count endl;Flag true;break;}if (Flag) break;}}return 0;
}
