物理

【信息机房】信竞知识普及

自古沙发归作者

如果要进行初级学习，可以参考oi维基进行初级知识学习

这帖子可以，你可以详细讲一讲动规和贪心，生物信息那边需要

我都快忘没了哈哈哈哈

dp动态规划

（应 这个可以有 讲解）

注：此文内容以作者本人观点+网上参考资料为主，如有问题可及时提出

动态规划可以理解作递推的一种，只不过动态规划（以后简称dp或动归）

大多数时候可以简化为三步骤：

1.设计状态

这一步通过字面意思，可以理解为：为一个你想要求的答案准备一个状态来表示它。

在这里解释不太清楚，请访问如下题目：https://www.luogu.com.cn/problem/P1048

或简化题面：给定n个物品，给了一个时间T，然后每个物品都给出一个价值和选择所需的时间t（每个物品仅能选一次，也可不选），求在不超过时间T的情况下最多可以获得的价值

此题状态即可设为dp[i][j],表示在前i个物品中选择了总时长不超过j的最大价值

状态设计好就是关键，但状态往往需要进行优化，比如这道题，因为第i个物品选择仅可能与i-1所处状态（即dp[i]与dp[i-1]）有关，也就是第i-2位就没有用处了，即可试图压缩第一维i，此处不多讲解，之后再说。

2.状态转移方程

状态转移方程就是根据状态转移过来，即根据一个已知状态推导出下一个状态。

比如还是上文这道题，状态转移方程为：

dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+v[i])

其中i为物品编号，j为时间，t[i]为第i个物品所需时间，v[i]为第i个物品价值

可以简单理解，在max中（默认你会部分基础，所以不多讲述一些基础知识，但可以发出询问）

第一项即可理解为不做选择（即不选择第i个物品）

第二项理解为做选择（即选择第i个物品），代价是t[i]，但价值为v[i]，需要寻找上一行状态预留t[i]的时间的最大价值再加上当前状态

3.初始化和求解

初始化中，需要考虑你的状态方程是如何设计，然后在没有任何状态下的初始值

比如这道题，因为在不做选择时价值为0，所以应初始化：

dp[0][0]=0;

但是对于dp其他的状态，需要根据转移方程来进行初始化，比如：

dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+v[i])

因为要取max，所以多用极大值来初始化，不多讲解

求解中，考虑题意中要求的状态是哪个，这道题就是满状态，即

dp[n][T]

其他题可能因题而异，甚至可能还会有求和、最大值等，不多讲解

动归主体就是这些内容，但是动归可不止这些，在普通动归的前提下延伸出很多，比如和图论结合形成树形dp等，这些之后有想了解者可以问问。

感谢观看

llwf 2025.05.30

尾注：端午假期快乐!

（排版如果不合适可以提出，下次修正）

如果需要的话，代码方面可以交给我

在下24年省一[嘿嘿😜]

贪心算法（这个可以有 赞助 提议讲解）

贪心算法是一种很 “名副其实” 的算法，因为它的本质就是如同咱们的思想一样，每一步都选择当前最优解。

当然有人就会有疑问了：“那这样思考，不会出现错误吗？难道这样就一定是最优解吗？”当然不是了。

经典栗子就是如同你玩游戏，你选择了可能当前最优的装备，但你越到后面可能会感觉从这个装备开始走的分支不再是最优，所以你便被 defeated 了。

贪心算法典型不能用的题目就是上文所说，也就是每一种选择都会对之后的选择产生影响，那么这种题一般不可用贪心。

来道经典题目：

石子合并：有n堆石子，每堆石子大小不同，你的任务是每次合并任意两堆，问你最小代价（每次合并的代价就是两堆石子大小之和）

肉眼便可分析出来，这道题是典型两次决策之间没有任何联系的题目，使用高贵的脑子一分析，拍案怒起表示，每次要合并最小的两堆，这样总代价就是最小的，因为你越早合并出更大的石堆，在最后累积这个石堆的代价便会更大，所以还不如从小合并。

那么这道题的正解就是通过对所有石堆进行从小到大的排序，然后从前到后依次合并，计算总代价。

贪心核心本质已经说完，但是它也是有无限潜力的，它可以同很多算法合并，组合出最优算法（即使它本身不一定最优，但合起来就是最优算法）。

感谢聆听，之后也会同步到CSDN上进行教学。

2025.6.6

（这次使用markdown，平板上感受不佳请提出）

我支持