题目链接：https://www.acwing.com/problem/content/5/
最近没有比赛可打，好好看看基础。
多重背包的朴素写法很简单，基本上都能写，复杂度nmk级别的，在数据量几千的情况下就处理不了了。
因此我们考虑用空间换时间，对物品进行二进制优化，...
12 多重背包的二进制优化
陈小白 2022.08.12 算法相关 抢沙发 10人打酱油
11 最长公共上升子序列 加强理解版
陈小白 2022.08.11 算法相关 抢沙发 9人打酱油
题目链接：https://www.acwing.com/problem/content/description/274/
两个序列a,b求最长公共上升子序列
我们定义f[i][j]为a序列的前i个和b序列的前j个元素的最长公共上升子序列
那么当前的f[i][j]可以继承f[i-...
11 AcWing 187. 导弹防御系统（LIS，贪心，dfs，迭代加深）
陈小白 2022.08.11 算法相关 抢沙发 9人打酱油
题目链接：https://www.acwing.com/problem/content/description/189/
为了对抗附近恶意国家的威胁，R国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直严格单调上升要么一直严格单调下降。
例如，一套系统先后拦...
09 oi普及组 防御法阵（背包预处理+区间dp）
陈小白 2022.08.09 算法相关 抢沙发 13人打酱油
题目链接：https://ac.nowcoder.com/acm/contest/21865/D
大意是给出n个城墙，每个城墙有一定数量的法阵，破坏他们可以获得经验值，同时消耗时间。每个城墙有一个固定的最大停留时间。且最多可以破坏m个城墙。当破坏掉一个城墙后，它邻近的城墙的经验值将增...
06 Educational Codeforces Round 133 (Rated for Div. 2)
陈小白 2022.08.06 算法相关 抢沙发 40人打酱油
比赛链接：https://codeforc.es/contest/1716 A了两道题A和B，速度还可以，但是CD态度太大一个也没做出来。 A题：给出一个数n，从0点开始到n点，每次只能走2步或3步，也可以回退。求最少多少次可以走到n点。 很简单，我们优先考虑3，如果是3的倍数可以直接/3过...
14 P1280 尼克的任务
陈小白 2022.07.14 算法相关 抢沙发 31人打酱油
题目链接：https://www.luogu.com.cn/problem/P1280
大意，给出一个时间n和任务数k
每个任务给出开始时间和持续时间。求最大的休闲时间。
很明显这个题是一个线性动态规划的题，但是却不好推导状态转移公式，尤其是有任务的时候，状态转移公式很难...
14 P1020 [NOIP1999 普及组] 导弹拦截
陈小白 2022.07.14 算法相关 抢沙发 31人打酱油
深夜更一波啊。明天任务，分别A一道二分，线性dp和搜索题
题目链接：https://www.luogu.com.cn/problem/P1020
大意：给出一组数据，求出这种数据的最长不升子序列以及至少多少个这样的不升子序列个数。
思路：前半个题最长不升子序列正常线性dp...
12 P2196 [NOIP1996 提高组] 挖地雷
陈小白 2022.07.12 算法相关 抢沙发 32人打酱油
题目链接：https://www.luogu.com.cn/problem/P2196
大意：有n个地窖，每个地窖里有一些地雷，给出第i个地窖到i+1-n的连通性。求出最优解及路径，要求拆除地雷最多。
这个题可以爆搜（因为n的值很小），也可以dp（类似于最长子序列那种，这里不同...
题目链接：https://www.lanqiao.cn/problems/1027/learning/
一道dp题，但是用普通三维dp最多只能的30%的测试点，记忆化搜索同理。
快筛一遍质数，然后用三维dp再然后剪枝可以过40%测试点的样子。
给出大佬的代码：https://b...
25 洛谷 P1802 5 倍经验日
陈小白 2022.06.25 算法相关 抢沙发 43人打酱油
题目链接：https://www.luogu.com.cn/problem/P1802
题目背景
现在乐斗有活动了！每打一个人可以获得5倍经验！absi2011却无奈的看着那一些比他等级高的好友，想着能否把他们干掉。干掉能拿不少经验的。
题目描述
...
05 最大子段和 三种解法 ：分治、贪心、dp
陈小白 2022.04.05 算法相关 抢沙发 92人打酱油
题目链接：https://www.luogu.com.cn/problem/P1115
如题，先分析复杂度。n的范围是2*10^5，对应之前总结的复杂度问题，nlogn可以解决10^5，这个题能解决一半
从而这个题只能考虑n线性计算的复杂度，这里贪心算法和一维dp可以解决，两个...
题目链接：https://www.lanqiao.cn/problems/1507/learning/
一道小小思维的dp题
要弄明白3个操作对应的数据的位置
先说说为什么要从i+1j+1开始计算呢，因为我们初始化默认第一个元素相等更容易操作
其实如果从ij开始计算...
先转发
https://blog.csdn.net/yc_cy1999/article/details/106106912?spm=1001.2101.3001.6650.5&utm_medium=distribute.pc_relevant.none-task-blog-2...
29 蓝桥杯 最长公共子序列
陈小白 2022.03.29 算法相关 抢沙发 85人打酱油
题目链接：https://www.lanqiao.cn/problems/1189/learning/
关于序列、子串这类问题挺多的，往往这些思想可以移植到别的地方，如一些dp或者贪心的题
这个题应该不是第一次做了，但还是没能做出来
dp的公式真是神奇而又巧妙==orz了...
题目链接：https://www.lanqiao.cn/problems/1461/learning/
怎么说呢，这个需要递推公式，奈何本人愚钝，没看出来w(ﾟДﾟ)w
1个砝码1个值
2个砝码4个值
3个砝码13个值
n=n*3+1
上代码
...
21 洛谷提高组 邮票面值设计
陈小白 2022.03.21 算法相关 抢沙发 148人打酱油
题目链接https://www.luogu.com.cn/problem/P1021
又是被oi支配的一天
两种解法，一种是双重暴力，一种是dfs+dp
啊啊啊，太难了。一个都理解不了，有时间再看
暴力
#include<iostream>
#...
有买的印章数和印章种数两个变量，就自然而然地想成二维数组dp[i][j]
关键是状态转移方程
这里参考https://blog.csdn.net/okok__TXF/article/details/121099645?ops_request_misc=%257B%2522req...