三金老师

题解

/ 注册

全部文章 / 题解（共7篇）

【每日一题】过河 (dp / 数据压缩)

Solution题意:题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。范围：st 属于[1,10], 石头数量<=100, L<=1e9思路：很明显的dp题，dp[i]维护到达 i 点的最少步数：但是要考虑到木板的...

每日一题 DP

2020-05-13

0 834

【每日一题】「火」皇家烈焰 (dp / 递推)

Solution题意: 0：这个格子没有烈焰，且其左右两个格子均没有烈焰 1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰 2：这个格子没有烈焰，且其左右两个格子中均有烈焰 *：这个格子有烈焰？：未告诉你本格情况求满足条件的方案数。思路：考虑用表示第 i 个字符是/不是火焰以...

每日一题 DP

2020-05-10

0 684

【每日一题】合并回文子串 (dp / 字符串回文)

Solution安利一下我的线性dp博客：https://blog.csdn.net/JiangHxin/article/details/105184169一般情况下，动态规划的解题步骤是：第一步：根据原问题和子问题来确定状态（dp数组表示什么东西）第二步：根据状态确定状态转移方程（怎样求解dp数组...

回文每日一题字符串 DP

2020-05-05

1 838

【每日一题】美味菜肴 (dp / 01背包)

Solution题意：给出m道菜，有a,b,c属性，美味值是a-b*c,求T时间能制作出菜肴的最大价值和。规定条件范围内的最大价值和/方案数，妥妥背包~跟国王游戏很像，每道菜的价值跟选取的顺序有关，所以要预处理出每道菜的顺序。考虑任意两道菜x和y的价值： x煮完后再煮y : y煮完后...

每日一题背包 DP

2020-04-28

0 849

【每日一题】Removal (dp+思维 / 子序列计数)

Solution题意：给出n个元素，每个元素不大于k，求删除m个元素后的子序列个数。子序列问题，通常可以联想到dp来做，考虑维护前 i 个元素删除 j 个元素的方案数，考虑第 i 个元素删或者不删，即有：但是这样计算的话肯定会有重复的方案，拿样例2来说：4 2 21 2 1 2删除第一...

每日一题思维 DP

2020-04-24

0 681

【每日一题】树 (dp)

Solution因为是树，所以保证任意两点都可以到达，所以可以选择从一个叶子节点作为出发点思考，表示这个叶子节点所在包含了 i 个节点的子图染了 j 种颜色的方案。考虑当前取的颜色是否和前次取的颜色一样，就是两种决策：若取的颜色相同则：若取的是新的颜色,则有种新颜色可以选择，则： ...

每日一题 DP

2020-04-06

4 1475

【每日一题】数学考试 (前缀和+dp)

Solution鬼鬼，鬼知道我这道题做了多少次，一直卡在83，今天才发现ans的初始值没处理好，一开始ans初始化为0一直过不去，这么多天终于过了。取区间里两段长度为k的子区间使和最大，肯定是dp。设pre[i]前i个数的长度为k的区间的最大和，那么只要遍历的时候再加上i-k的另一段k区间就可以了。...

每日一题 DP 前缀和

2020-04-02

0 684