陕西省网上注册公司流程,性价比高seo网站优化,wordpress网站如何与关联,天津室内设计学校代码部分前有一千六百字了
P1941 [NOIP2014 提高组] 飞扬的小鸟 考察对背包 dp 算法过程理解的透彻性。过程透彻性也是解决所有问题的关键#xff08;建立在算法已学的基础上#xff09;。 n , m n,m n,m 的范围足够我们 O ( n m ) O(nm) O(nm) 的遍历整个地图。设 f i , …代码部分前有一千六百字了
P1941 [NOIP2014 提高组] 飞扬的小鸟 考察对背包 dp 算法过程理解的透彻性。过程透彻性也是解决所有问题的关键建立在算法已学的基础上。 n , m n,m n,m 的范围足够我们 O ( n m ) O(nm) O(nm) 的遍历整个地图。设 f i , j f_{i,j} fi,j 表示到 ( i , j ) (i,j) (i,j) 格子时的最小点击数考虑转移共两种情况分别是由前一个格子下移即不动或上移 x x x 次得到的。由于下移操作只有选或不选两种情况我们可以把下移操作当作 01 背包来转移即 f i j min ( f i , j , f i − 1 , j d o w n [ i − 1 ] ) f_{i}{j}\min(f_{i,j},f_{i-1,jdown[i-1]}) fijmin(fi,j,fi−1,jdown[i−1])。
上移操作可以进行多次如果对于每个格点上移操作分别进行 0 0 0 至 m / u p [ i ] m/up[i] m/up[i] 次的转移显然会超时观察发现单独对 f i , j f_{i,j} fi,j 进行上移操作的转移时 f i , j min ( f i , j , f i − 1 , j − u p [ i − 1 ] × x ) f_{i,j}\min(f_{i,j},f_{i-1,j-up[i-1]\times x}) fi,jmin(fi,j,fi−1,j−up[i−1]×x) 与 f i , j min ( f i , j , min ( f i − 1 , j − u p [ i − 1 ] , f i , j − u p [ i − 1 ] ) ) f_{i,j}\min(f_{i,j},\min(f_{i-1,j-up[i-1]},f_{i,j-up[i-1]})) fi,jmin(fi,j,min(fi−1,j−up[i−1],fi,j−up[i−1])) 的本质相同而这正是完全背包算法过程的关键。
既然本质相同那么转移方法便与完全背包保持一致性。注意到由于每个点不能同时选择上移和下移而上移操作的转移用到了 f i , j − u p [ i − 1 ] f_{i,j-up[i-1]} fi,j−up[i−1] 即当前列某一位置的值由上可知在对上移操作的转移中使用到的 f i , j − u p [ i − 1 ] f_{i,j-up[i-1]} fi,j−up[i−1] 不能包含下移操作的更新即使用到的 f i , j − u p [ i − 1 ] f_{i,j-up[i-1]} fi,j−up[i−1] 必须只包含上移操作的更新状态。
那么这里有两种方法一种是将两次操作的转移分开因为下移操作的转移需要用到的 f i − 1 , j − 1 d o w n [ i − 1 ] f_{i-1,j-1down[i-1]} fi−1,j−1down[i−1] 为前一列的值且两种操作的转移都不会干扰前一列的值所以可以先更新上移操作再更新下移操作。
另一种是新增一维状态设 f i , j , 0 / 1 f_{i,j,0/1} fi,j,0/1 表示 ( i , j ) (i,j) (i,j) 由上一列下移 /上移得到。思维量很小但显然没有第一种方法简便。我用的就是这种
注意上移时高度到了 m m m 将无法再上升但和 0 0 0 处不同冲到 m m m 高度不会使游戏结束。 所以转移时高度超过 m m m 的部分要参与 dp 并转移至 m m m 那。
最后考虑柱子和是否能通关的判断。对于柱子首先记得排序可以在转移完毕之后将柱子所在处的 f f f 值再赋为 inf \inf inf也可以干脆在转移过程前标记转移时就特判掉并跳过当然也不可以不这么麻烦猜对了我就这么敲的调半天不对
通关判断就很简单了转移完扫一遍当前列有没有解到不了就退出通过柱子数为当前柱子编号 − 1 -1 −1当前列过不了肯定说明有柱子因为无论如何都可以一直按屏幕保持在 m m m 高度当前柱子过不了自然过了的柱子就是编号 − 1 -1 −1 了。
时间复杂度 O ( n m ) O(nm) O(nm)。 空间复杂度 O ( n m ) O(nm) O(nm)可以滚掉一维故为 O ( m ) O(m) O(m)。
#includebits/stdc.h
using namespace std;
int n,m,k,up[10005],down[10005],f[2][2005][2];
struct qh{int p,l,h;bool operator (const qh T)const {return pT.p;}
}a[10005];
inline int Rd(){int s0,w1;char chgetchar();while (ch0||ch9){if(ch-) w-1;chgetchar();}while (ch0ch9) s(s1)(s3)ch-0,chgetchar();return s*w;
}
int main(){nRd();mRd();kRd();for(int i0;in;i) up[i]Rd(),down[i]Rd();for(int i1;ik;i) a[i](qh){Rd(),Rd(),Rd()};sort(a1,ak1);
// for(int i1;ik;i) printf(%d %d %d\n,a[i].p,a[i].l,a[i].h);int z0;for(int i1;in;i){for(int j1;jm*2;j) f[i%2][j][0]f[i%2][j][1]1e9;for(int j1;jm*2;j){if(jdown[i-1]m) f[i%2][j][0]min(f[(i-1)%2][jdown[i-1]][0],f[(i-1)%2][jdown[i-1]][1]);if(j-up[i-1]0) f[i%2][j][1]min(f[i%2][j-up[i-1]][1],min(f[(i-1)%2][j-up[i-1]][0],f[(i-1)%2][j-up[i-1]][1]))1;}for(int jm1;jm*2;j) f[i%2][m][1]min(f[i%2][m][1],f[i%2][j][1]);if(a[z1].pi){z;for(int j1;ja[z].l;j) f[i%2][j][0]f[i%2][j][1]1e9;for(int ja[z].h;jm*2;j) f[i%2][j][0]f[i%2][j][1]1e9;
// printf(%d %d %d %d\n,z,a[z].p,a[z].l,a[z].h);}int mn1e9;for(int j1;jm;j) mnmin(mn,min(f[i%2][j][0],f[i%2][j][1]));
// for(int j1;jm;j) printf(%d %d ,f[i%2][j][0],f[i%2][j][1]);puts();if(mn1e9) return printf(0\n%d,z-1),0;}int ans1e9;for(int i1;im;i) ansmin(ans,min(f[n%2][i][0],f[n%2][i][1]));printf(1\n%d,ans);return 0;
}
/*
start coding:09:44
finish debiuging:11:05
*/附上题目
[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。 start writing:19:00 finish the work:20:33
