[编程笔记]-Huffman_Tree(Greedy)哈夫曼树（贪心）
前言本文并非对数据结构哈夫曼树的详细讲解（不然就会放进数据结构里了），而是对贪心问题中哈夫曼树有关思想题目的讲解。 还没创建hhh 例题对没有概念（贪心算法还能有概念？就是每次找局部最优解嘛；哈夫曼树详见哈夫曼树页面），直接给例题。AcWing148-合并果子 还记得石子合并吗？它们两道题的区别是，合并果子不用相邻的两堆。 毫无疑问，最优解肯定是每次选最小的两堆进行合并，以消耗最小的能量。 这就让
![[编程笔记]-Huffman_Tree(Greedy)哈夫曼树（贪心）](/img/cpp1.png)
[编程笔记]-Interval_Problem(Greedy)区间问题（贪心）
前言鉴于这篇博客目的，我们就挑一些代码量短但是思维难度不低的问题讲。 没错，和DP一样，因为没有具体的套路模板，就直接上例题了。 这篇算作一个大整合，整合了大部分贪心结局的区间问题。 例题区间选点原题链接贪心嘛，就是要贪心一点，想一个最贪心的算法。 对于每一个区间，如果不用选，那最好；要是要选，那就直接选最右边的点。（记得按右端点从小到大排序） 只要排好了序，每次都选最右边，能覆盖的区间一定是最多
[编程笔记]-Memory_Search记忆化搜索
前言说实话，这个记忆化搜索呢，硬要说的话，你可以说它是“图型DP优化”（我编的hh） 就是在图论之中搜索然后去除不必要的递归嘛，就是DFS/BFS套个壳。 但毕竟更像是DP，所以就放这吧（树型DP都在呢不是吗） 例题AcWing901-滑雪f[i][j]表示从(i,j)开始滑的最长路径。 从上下左右四个方向找就行了。 12345678910111213141516171819202122
[编程笔记]-Tree_DP树形DP
概念就是在树上进行DP。（是不是有点废话hhh） 例题鉴于DP的特殊性，直接上例题解释吧。AcWing285-爽得要死的舞会 设计状态： f[u][0]：以u为根的子树中（不含u）最大的快乐值。 f[u][1]：以u为根的子树中（含u）最大的快乐值。 那么肯定是从子树转移来的嘛。 当不含u时，子节点含不含无所谓；当含u时，子节点只能不含了（倒反天罡了hhh应该改名没有下属的舞会） 123456
[编程笔记]-State_Compression_DP状压DP
概念把状态压缩成（二进制）整数表示的动态规划，通常情况下每一位上的数字表示当前状态这个位置的元素属性。 例题没错还是直接上例题了。 蒙德里安的梦想AcWing291-蒙德里安的梦想 至于思路，我们考虑一列一列从左到右思考。 我们只要求出所有合理的横着的方块摆放情况，就可以得到答案。 对于每一列，我们记录当前状态为表示整个数列每一行是否有以这一行这一列为左半部分的横方块（向右一列伸出）。 对于每一列
[编程笔记]-Digital_DP数位DP
前言要不是见到，我绝对不会把这种数奥题和信竞联系在一起。 甚至小学数奥hh 概念统计数字每位上数字出现的次数。 解释不便，直接给题。 AcWing338-计数问题 #解决我们就可以想到前缀和了。 count[i][j]表示从第1个数到第i个数出现的j的个数。 这就是大致思路。假设当前数字是abcdefg，当前查找数字是x。 那么我们只需要求出在1~n个数中，x在不同数位分别出现的次数即可。 举个例
[编程笔记]-Count_DP计数DP
概念状态记录数量的DP。 对就是这么朴实无华。 例题AcWing900-整数划分 方案一基础版首先设计状态：f[i][j]表示在从1~i的数字中能够组成j的组合数。 状态转移：根据选择几个（令为k）第i个数，可以直接转换： f[i][j]+=f[i-1][j-k*i] 1234567891011121314151617181920212223#include<bits/stdc++
[编程笔记]-Interval_DP区间DP
概念区间DP，在定义状态时，往往定义的是一个区间的情况（不同于线性，线性往往定义的是单个点情况）。具体的，区间DP表示的区间可以重叠，并且可以由另外的有关区间转化而来。 例题AcWing282-石子合并LuoguP1775-石子合并 12345678910111213141516171819202122232425262728#include<bits/stdc++.h>using n