🎃 1.打包（二分答案）
Lazy有N个礼物需要打成M个包裹，邮寄给M个人，这些礼物虽然很便宜，但是很重。Lazy希望每个人得到的礼物的编号都是连续的。为了避免支付高昂的超重费，他还希望让包裹的最大重量最小。
题目链接：打包 http://lx.lanqiao.cn/problem.page?gpid=T2978
题目的意思有一点容易理解错（蓝桥题目特色，生怕你读懂哈哈哈），刚开始我还以为选一个长度为M的子数组保证和最小。但其实它的意思是将N个礼物分成若M个包裹，每个包裹可以有若干个礼物，然后让我们求这些包裹中最大重量最小的值。
像这种求某某某最大的最小值，或者最小的最大值大家一定要想到二分。很多人肯定心想，切二分嘛，套个模板不就好啦。确实是套个模板不就好了，但是对于二分的题目是分为两种，一种是求值二分，而另外一种就是二分答案。直接对答案去进行二分查找，所以这题我们直接对包括的最大重量的最小值这个属性进行二分，所以问题来了，如何确定边界和check函数逻辑？
对于左边界left，它肯定是我们所有礼物中最重礼物的重量，因为礼物必须全部打包，最重的包裹在最轻的情况下就是只单独选最重的礼物
对于右边界right，我们直接考虑极限情况，全部礼物的重量的总值就好，既然是二分，只有答案能在区间里，那就肯定能找到答案
至于最核心的check函数，无非则是判断选择当前重量，能否分成至多M个包裹，每次选择连续且重量之和不超过mid的的礼物打包为一个包裹，最后的包裹数量小于等于M说明符合，我们让r=mid，否则l=mid+1.
代码转换：
import java.util.Scanner; public class Main { static int N=100010; static int[] arr=new int[N]; static int n,m; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); int max=0; int sum=0; for(int i=1;i<=n;++i) { arr[i]=sc.nextInt(); sum+=arr[i]; max=Math.max(max, arr[i]); } int l=max; int r=sum; while(l<r) { int mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } System.out.println(l); } static boolean check(int target) { int count=0; int tmp=0; for(int i=1;i<=n;++i) { count+=arr[i]; if(count>target){ count=0; tmp++; i--; }else if(i==n){ tmp++; } } return tmp<=m; } }
👻2. 跳跃的小明（动态规划）
有一条长为n的走廊，小明站在走廊的一端，每次可以跳过不超过p格，每格都有一个权值wi。
小明要从一端跳到另一端，不能回跳，正好跳t次，请问他跳过的方格的权值和最大是多少？
题目链接：跳跃的小明http://lx.lanqiao.cn/problem.page?gpid=T770
比较明显的DP问题：
- 状态表示：F[i][j]：通过j步走到第i格的最大权值
- 转移方程分析：分析最后一步是通过走了跳了第几格到达第i格。如果最后一步是通过跳跃1格到达第i格，那么转移方程应该是，w[i]是第i格的权值。如果最后一步是通过跳跃2格，则转移方程是：。最多是通过跳跃p格到达第i格，我们只需要在这么多方案中取一个最大值即可。
- 初始化：由于权值是带有负数的，所以我们首先需要将所有方案初始化成负无穷，然后初始化第一步走一格一直到第一步走p格的情况。最后答案是f[n+1][t]，因为对于给定的数组其实左右两头有两个权值为0的位置，那才是我们的起点和终点。
代码转换：
import java.util.Arrays; import java.util.Scanner; public class Main { static int N=1010; static int n,p,t; //通过j步走到第i个格子的最大权值 static int[][] f=new int[N][N]; static int[] arr=new int[N]; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); p=sc.nextInt(); t=sc.nextInt(); for(int i=1;i<=n;++i) arr[i]=sc.nextInt(); for(int[] a:f) { Arrays.fill(a,-0x3f3f3f); } //初始化：通过第一步能走到的位置 for(int i=1;i<=p&&i<=n+1;++i) f[i][1]=arr[i]; //走到第i格 for(int i=1;i<=n+1;++i){ //通过j步 for(int j=2;j<=t;++j){ //上一次走了k步到达第i格 for(int k=1;k<=p&&k<=i;++k) { f[i][j]=Math.max(f[i-k][j-1]+arr[i],f[i][j]); } } } System.out.println(f[n+1][t]); } }
🎆3.大胖子走迷宫（BFS）
题目链接：大胖子走迷宫 http://lx.lanqiao.cn/problem.page?gpid=T2739#submitpanel
比较经典的BFS问题，稍微属于一点变种的BFS，首先大家要认真理解题目的意思，摒弃掉我们平常做BFS问题的思维，首先思考以下几个问题：
1.每次行动的决策，是否只能是上下左右移动？
2.对于能否移动的判断，我们应该如何判定？
疑问解答：
1.由于在某些地点，可能因为小明太胖而走不过去，而这条路径却是唯一的路径，所以小明得在原地等待变小后再通过，或者其实小明走其他路还不如在原地变小再过去，所以在上下左右移动的决策中，还应该加上原地等待
2.由于小明太胖，所以他占用的区域可能是5X5或者3X3，所以我们在移动到（x，y）坐标时，不仅需要判断x,y和合法坐标，还得判断以x,y为中心周围的3x3或者5x5都得是合法的。这样我们可以用一个变量count记录成小明的膨胀因子，每次判断是否合法时，都需要在原坐标上加上或者减去膨胀因子，最开始是5x5，所以膨胀因子为2，当变成3x3时，膨胀因子为1，最后变回原形以后膨胀因子则变为0。
