不要为打翻的牛奶哭泣

分类

题解(1)

/ 注册

全部文章（共46篇）

题解 | 能量项链

区间dp1）构建二维数组dp[n][n]，dp[i][j]代表以i为起点，j为终点的区间的最优解。2）按照序列长度从1到n，起点从1到n-1的顺序二层循环3）状态转移方程：dp[i][j] = maxj dp[i][k] + dp[k][j] + nums[i] * nums[k+1] * nums...

2025-04-30

0 6

题解 | 取数游戏

这题应该是前面DP49的简化版，不需要高精度，令dpl,rdpl,r表示左侧取ll个，右侧取rr个的最大值，那么可以得到状态转移方程：dpl,r=max⁡(dpl−1,r+al×bi,dpl,r−1+an−r+1×bi)dpl,r=max(dpl−1,r+al×bi,dpl,r−1+an...

2025-04-30

0 8

题解 | 旅游

可以用树型dp，对于某一个结点，是否选择这个点进入集合，我们用dp数组表示，dp[i][0]dp[i][0]表示以ii结点为根的子树，不选取该结点时的最大独立集的数量，dp[i][1]dp[i][1]则表示以ii结点为根的子树，选取该结点时的最大独立集的数量，那么dfs构建这个dp数组以后，dp[s...

2025-04-30

0 18

题解 | 红和蓝

叶子节点之与父亲有边相连，所以叶子节点必然与父亲同色。而父亲节点已经和叶子节点同色，所以叶子节点必然与爷爷节点异色。爷爷的颜色确定后，如果爷爷还与一条边相连，那么标记爷爷的相邻点颜色也确定。对于任何一条路径，可以这样递归上去。所以统计同色（友）信息然后再跑一边DFS染色即可 #include <...

2025-04-30

0 7

题解 | 小红的树

关于第一个改动使运行速度提升的原因，在查阅vector相关资料后并没有直接的回答。我个人的理解是，vector本身是对数组的封装，其低层实现就是数组，为了保证动态性，执行效率肯定比数组低。第一种定义方式定义了一个二维动态数组，而第二种定义方式虽然定义的也是一个二维数组，但其一维是固定的，一维是动态的...

2025-04-30

0 7

题解 | 跳台阶扩展问题

这里的青蛙比前面两道题的青蛙更厉害一些，他一次可以跳1阶，2阶，3阶……。所以要想跳到第n个台阶，我们可以从第1个台阶跳上来，也可以从第2个台阶跳上来……，所以递推公式是f(n)=f(n-1)+f(n-2)+……+f(2)+f(1);同样如果我们想跳到第n-1个台阶，也可以列出下面这个公式f(n-1...

2025-04-30

0 9

题解 | 最小花费爬楼梯

如果到第i个台阶，我们可以从第i-1个台阶跳一步上来，也可以从第i-2个台阶跳两步上来。哪个花费少我们就选择从哪个跳上来。我们定义dp[i]表示到第i个台阶需要的最小花费，那么我们可以得出递推公式dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] ...

2025-04-30

0 7

题解 | 矩阵的最小路径和

到达出口只能从出口左边或者上边来，这样就很容易写出递归式,并且进行记忆化搜索。也可以使用状态方程dp[i][j]=min(dp[i−1][j],dp[i][j−1])+v[i][j]dp[i][j]=min(dp[i−1][j],dp[i][j−1])+v[i][j] 进行递推，处理好边界即可。 #...

2025-04-30

0 6

题解 | 拦截导弹

Q1：很明确就是最长递减子序列的长度Q2：根据Dilworth定理:最少的下降序列个数就等于整个序列最长上升子序列的长度 n=eval(input()) heights=list(map(int,input().split())) dp=[1]*n # Q1:最长递减子序列 dp2=[1]*n # ...

2025-04-30

0 5

题解 | 不相邻取数

不相邻取数的最小场景就是间隔1个取数和间隔2个取数（间隔3个的可以看成是 2个间隔1个的取数，以此类推）所以我们只需要记录 dp[i] = max{aiai+dp[i-2] , aiai+dp[i-3]}最大值一定位于 n或者 n-1中（从1开始） #include<stdio.h>...

2025-04-30

0 6