蓝桥杯 2022年省赛真题
Java 大学A组
- 试题 A: 裁纸刀
- 试题 B: 寻找整数
- 试题 C: 求和
- 试题 D: GCD
- 试题 E: 蜂巢
- 试题 F: 全排列的价值
- 试题 G: 青蛙过河
- 试题 H: 因数平方和
- 试题 I: 最优清零方案
- 试题 J: 推导部分和
??小做一会 J A mathrm{JA} JA 打发时间。
试题 A: 裁纸刀
本题总分： 5 5 5 分
【问题描述】
??小蓝有一个裁纸刀，每次可以将一张纸沿一条直线裁成两半。
??小蓝用一张纸打印出两行三列共 6 6 6 个二维码，至少使用九次裁出来，下图给出了一种裁法。
??在上面的例子中，小蓝的打印机没办法打印到边缘，所以边缘至少要裁 4 4 4 次。另外，小蓝每次只能裁一张纸，不能重叠或者拼起来裁。
??如果小蓝要用一张纸打印出 20 20 20 行 22 22 22 列共 440 440 440 个二维码，他至少需要裁多少次/p>
【答案提交】
??这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
443
??我们可以仿照两行三列时，题目给出的切分法，写出一个递归程序去计算它的切割次数，
??题目给出的方法可以抽象为两部分，
?? 1 、 1、 1、边缘裁剪 4 4 4 次。
?? 2 、 2、 2、选择当前纸片中连接二维码数量最多的一条线，沿其切割，分割成两个小纸片，重复此步直至纸片的某行或某列为 1 1 1。
??当然这种方式并非绝对最优，一种较为稳妥的方式是在记忆化处理下暴搜，不过总所周知，记忆化搜索是状压 d p mathrm{dp} dp 的递归实现，由此，我们可以在状态转移方程上研究出最优方案之间的共性，
??设状态 f i , j f_{i,j} fi,j? 为 i i i 行 j j j 列的纸片在最优裁剪方案下的步骤数，显然有 f i , j= f j , i f_{i,j} = f_{j,i} fi,j?=fj,i?、 f i , 1= i ? 1 f_{i,1} = i-1 fi,1?=i?1、 f i , j= min ? { f i ′ , j+ f i ? i ′ , j, f i , j ′ + f i , j ? j ′ } + 1 ∣ 1 ≤ i ′ fi,j?=min{fi′,j?+fi?i′,j?,fi,j′?+fi,j?j′?}+1∣1≤i′i,1≤j′j，
??当我们知道 f i ′ , j+ f i ? i ′ , j f_{i’,j}+f_{i-i’,j} fi′,j?+fi
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！