算法导论其八：动态规划和贪心算法

动态规划

概述

动态规划并没有一个放诸四海皆准的公式。但是总而言之，它可以分为以下几个步骤进行设计。
1. 描述最优解的结构（也是最考验思维的一步，最优解由哪些值计算得出）
2. 递归定义最优解的值（状态转移方程）
3. 自底向上的计算最优解所需要的值
4. 由计算出的各个值构造出最终结果
优化：普通的动态规划并没有本质上比搜索强太多，即不一定能降低复杂度，可能只是常数上的一个改变。动态规划实际也有很多优化技巧。

最优子结构

定义：如果一个问题的最优解中，包含了子问题的最优解，就称该问题具有最优子结构。
- 具备最优子结构，是使用动态规划，贪心算法的必要条件。
- 最优子结构并不一定是直接就能看出来的，常常需要进行一定的构造，将原问题巧妙的描述。
寻找最优子结构的一些思路：
- 问题具有选择性，一个位置的选择会得到一个或多个需要解决的子问题。
- 先假设已经获得一个导致最优解的选择
- 确定在这种选择下，会发生哪些子问题，如何描述子问题所代表的搜索空间
- 可能存在具有多种子问题的情况，需要计算多个不同种类的子问题，来共同决定一个原问题的最优解

重叠子问题

定义：如果一个问题的求解过程中，可以反复求解完全相同（参数上下文）的子问题，而不是总在搜索全新的子问题，那么就说明该问题具有重叠子问题。
- 是重叠子问题，是动态规划可行的必要条件。
- 和分治法的对比：分治法总是在每一步产生全新的子问题。

无后效性

定义：在后续的状态转移的时候，只关心前面阶段的状态值，不需要关心这个状态是如何推导出来的。且某一次状态转移一旦确定，就不受之后阶段的决策影响。
一点理解：很多时候，无法直接使用动态规划的原因，并不是不具备重叠子问题。而是因为原始问题不具备无后效性导致的。即当前的决策不能保证不被推翻，它可能会和后续的某一次状态转移冲突，而被推翻。另一方面，后续的决策还可能需要保留当前决策的决策流程（维护额外的状态转移信息，显然会提高时空复杂度）。这里用题目使数组和小于等于 x 的最少时间举例。
1. 一个容易思考到的方法是：
  - 对于$dp[i][j]$，设其表示第i秒，清空位置j时，可以获得的最小总和。此时只需要对i、j遍历，就能得知满足要求的结果的出现时间。表面看是$O(n^2)$
  - 但是在状态转移时，i+1秒的第j位置，需要知道i-1秒各种情况的各个位置的具体情况，否则无法算出正确的总和（可能会把一个位置超额清空），因此需要再维护所有决策的详细信息，复杂度就来到了$O(n^3)$，不能接受
2. 上一个方法的问题有两点：状态的选择不够好、对清空位置的顺序没有控制
  - 状态值的选择：直接计算最小总和需要考虑的因素很多，如果反过来思考，只计算最大减少总和，就只需要考虑在什么时候清空一个位置。
  - 状态转移顺序控制问题：这是最根本的问题。首先用时间划分重叠子问题不够好，应该先对位置进行遍历。并且将位置提前排序。
3. 抽象来说，本质上还是需要对问题进行更多分析和思考。找到在某种状态维度划分下真正的最优子结构。（前k个，前k秒，前kX）

备忘录写法

记忆化搜索。动态规划的一种变形，既具有大体上等价于动态规划的效率，又采用了自顶向下的写法（更类似于搜索）。
写法：就是针对当前输入参数做问题记录，对于完全相同的输入参数，直接返回上一次的计算结果。

树上DP

动态规划的一种变形，为了适应题目中子问题之间的树结构。一般会综合其他树算法（如LCA）、动态规划（如背包DP）算法进行考察。
一般写法：从根开始DP，对子树递归返回一个DP数组，在根位置计算状态转移
参考:OI Wiki 树形 DP

优化

概述

空间优化：当你编程的时候发现，动态规划的状态存储数据结构中，有那么几个维度，只受到少数状态值（或者是最近几次状态值的影响），那么就可以进行空间优化。一般可以将数据结构降低一个$n$的指数级别。 - 例如：$f(i,j)=max_{0<j<n}\{f(i-1,j)+h_{\mathrm{某种代价}}(i,j)\}$。这里面，i所在的维度，显然没有存储的必要，在可以的情况下应当予以删除。 - 优化不需要过早，为了思路清晰，空间多一些一般无所谓。
时间优化：这是动态规划提升难度的地方。计划在后续的系列中，结合实际题目进行更新吧。

状态压缩DP：最经典的一类优化，将搜索空间的状态压缩为一个可遍历的集合，使得对于原来较为复杂难以遍历的空间，能够通过简单的方式进行枚举。最常用的就是二进制串来表示状态，例如
1. 在$N \times N$的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。对每一行，用二进制串来表示某个位置是否有国王。并不是所有二进制串都是有效的状态，需要先过滤，然后再对相邻行进行比对。
2. 枚举一个集合的全部子集。
压缩的结果大多可以表示为$dp[s]$，其中$s$代表了一种可能的状态。

数位DP：一类非常明显的题目。当题目考察内容是形如计算一个数字的各个数位满足一些条件时的统计信息。这种时候就是数位DP。典型题目：统计整数数目、统计特殊整数。教程可以参考OI-Wiki数位DP。这里给出统计特殊整数的典型解答。记忆化搜索是最常见，最好写的形式。

class Solution {
public:
    // #define N 11
    // #define M (1<<11)
    // int dp[N][M];
    unordered_map<int,int> dp;
    vector<int> nums;

    inline int combine(int index,int mask,bool limit,bool start) {
        int result=0;
        result=(index<<11) | mask | (limit<<16) | (start<<17);
        return result;
    }

    // 记忆化搜索
    int dfs(int index,int mask,bool limit,bool start){
        if(index==nums.size())
            return 1;
        // 合并index、mask、limit、start
        if(dp.find(combine(index,mask,limit,start))!=dp.end())
            return dp[combine(index,mask,limit,start)];
        int up=limit?nums[index]:9;
        int res=0;
        // cout<<index<<" "<<mask<<" "<<limit<<" "<<up<<endl;
        for(int i=0;i<=up;++i){
            if(mask&(1<<i))
                continue;
            // 注意前导0是可以重复的，此时不应当计入mask
            if(i==0&&!start){
                res +=dfs(index+1,mask,limit && i==up,false);
            } else {
                // i!=0 || start
                res +=dfs(index+1,mask|(1<<i),limit && i==up,true);
            }
        }
        dp[combine(index,mask,limit,start)]=res;
        return res;
    }

    int countSpecialNumbers(int n) {
        while(n){
            nums.push_back(n%10);
            n/=10;
        }
        reverse(nums.begin(),nums.end());

        // digit index, digit mask, limit
        return dfs(0,0,true,false)-1;
    }
};

插头DP：也称为连通性状态压缩DP，轮廓线DP。状态压缩的一些特例，不仅需要压缩状态，而且需要维护状态之间的连通信息。基本术语：轮廓线（已决策状态和未决策状态的分界线）、

骨牌覆盖，在一个$n \times m$的棋盘中，放置$1\ times 2$或$2 \times 1$的多米诺骨牌（即横放、竖放），问方案总数。参考HDU 1400 插头DP，状压DP。

// 状态压缩转移方程，dp[i][s]表示第i行覆盖状态为s时的方案总数
// 注意实际上，除了最后一行不一定全覆盖（因为可能还会有下一行），其他行在状态转移中必须满足全覆盖要求
// 也因此，在计算过程中，上一行有些状态的值会被抛弃（无法通过判断），因为下一行无法帮助其补齐全覆盖

// 覆盖状态的定义示例：对一个四列的棋盘，如s=0011
// 0 代表该格子是竖放矩形的上半部分，其他情况都是1（竖放矩形的下半部分，或水平放置）
// 检查上下行兼容的原则就是，判断此时能否将上一行的所有0都覆盖掉
// 若上一行为11000，下一行为00111，可以兼容，下一行右侧三个先空着
// 若上一行为10000，下一行为00111，不能兼容，第二列一定无法覆盖
// 若上一行为11100，下一行为11100，不能兼容，前三个肯定是冲突的状态
// 若上一行为11000，下一行为11100，可以兼容
bool check(int x, int y) {
    // 存在任意一列同时为0，必失败
    if ((x | y) != (1<<m)-1) {
        return false;
    }
    int count = 0;
    for(int i=0;i!=m;++i){
        if(x & 1 && y & 1){ // 两行同时为1，此时两行只能横放
            count++;
        } else { // 横放结束
            if(count & 1) // 不满足偶数个，无法满足横放
                return false;
            count = 1;
        }
        x>>=1;
        y>>=1;
    }
    return !(count&1); // 最后一次判断是否满足偶数个
}

// 边界情况，即初始行的上一行已经填满
dp[-1][(1<<m)-1]=1;

// 转移方程主体为
for(int i=0;i!=n;++i) {
    // 上一行的覆盖状态
    for(int s=0;s!=1<<m;++s) {
        // 本行的覆盖状态
        for(int t=0;t!=1<<m;++t) {
            // 检查上下行状态是否兼容
            if(check(s,t))
                dp[i][t]+=dp[i-1][s];
        }
    }
}

以上是普通的状态压缩DP写法，思路简洁（除了检查兼容的部分），如果使用轮廓线DP，则思路变为对于每一列，累计在不同状态下的转移，写法和思路如下轮廓线DP的状态示意

// 普通的状态压缩DP中，其实计算了过多的状态转移情况（获取的信息过多）
// 不考虑边界时，实际上对于每一个牌的放置方式，只需要考虑其左侧，和上侧的的棋盘格的情况
// 而如果从左至右处理各列，会在棋盘格上显示出一条轮廓线（折线），如上图所示
// 轮廓线以上，以左的，都是已经计算过的状态，
// 针对轮廓线上的状态进行状态压缩的DP，就是轮廓线DP
// 此时每一次枚举状态其实融合了多行的状态

// 状态的0、1的代表含义和上一个写法相同
vector<int> f0,f1;
f0.assign(m,0);
f1.assign(m,0);
f1[(1<<m)-1]=1;

// 转移方程主体为
for(int i=0;i!=n;++i) {
    for(int j=0;j!=m;++j){
        swap(f0,f1);
        f1.assign(m,0);
        for(int s=0;s!=1<<m;++s){
            // 该前置轮廓线状态是有正确方案的
            if(f0[s]) {
                // ! 优先于 +-*/ 优先于 >> 优先于 & 优先于 ^
                if(s >> j & 1) {
                    // 上一行该列已被覆盖，那么本行要么向左横放一个，要么不放
                    // 但横放需满足条件，即此时左侧是空着的
                    if(j>0 && !(s & 1<<j-1)) {
                        // 这里的位运算利用已知s>>j&1为1，此时s中j和j-1位都是1了，代表横放
                        f1[s ^ 1 << j-1] += f0[s];
                    }
                    // 不能放牌，将j位置0
                    f1[s ^ 1 << j] += f0[s];

                } else {
                    // 上一行该列未被覆盖，可以竖着放置，将状态中j位置为1
                    f1[s ^ 1 << j] += f0[s];
                }
            }
        }
    }
}

参考：插头 DP

例子

装配线调度

问题描述：
- 在工厂内经常有装配线用于组装一个产品，一条装配线上有多个装配站，当一个产品经过一个装配线上的所有装配站后就可以出厂了。设装配线编号为$i$，设第$i$条装配线上的第$j$个装配站为$S_{i,j}$。不同装配线上的相同位置的装配站，功能相同。即$S_{1,j}$和$S_{2,j}$功能相同。将装配站$S_{i,j}$的装配用时记为$a_{i,j}$。产品进入第$i$条装配线的时间为$e_i$，离开的时间为$x_i$。
- 不同的装配站速度可能完全不一样，即使他们是同一顺位的。而且正常情况下，装配线上的产品是不会变更装配线的，但是如果希望加快装配速度，则可以更换。将产品从$S_{i,j}$移走的时间为$t_{i,j}$。
- 请问一个产品从开始装配到结束，最快能多快呢？（方便起见，本文接下来的讨论中，装配线数量只有两个）
暴力解法：遍历所有的$2^n$种装配站的组合，计算每一种的用时。复杂度$O(2^nn)$。$j=1,2,….,n$
思考步骤：
1. 描述最优解的结构：考虑产品从起始点到装配站$S_{i,j}$的最快路线$f(S_{i,j})$。按顺序遍历所有的装配站即可。
2. 状态转移方程：$f(S_{i,j}) \gets h(S_{1,j-1},S_{2,j-1})$。更具体的来说，$f(S_{1,j})=min(f(S_{1,j-1})+a_{1,j},\ f(S_{2,j-1})+t_{2,j-1}+a_{2,j})$。
3. 自底向上计算：给出边界值$f(S_{1,1}) = a_{1,1} , \ f(S_{2,1}) = a_{2,1}$。
4. 最终结果：$min(f(S_{1,n}), \ f(S_{2,n}))$。
额外的话：
1. 描述最优解的结构，这是非常考验算法能力的一步。说太多的方法论都是空话，这个东西就是多看多练就好了。
2. 有一种值得一试的思路，就是从递归的反向思维出发。正常是计算当前的用时，然后递归调用接下来去往哪个装配站。而动态规划的解法恰恰相反，是从当前装配站的来源来考虑。

矩阵链乘法

描述：给定$n$个要相乘的矩阵构成的序列$<A_1,A_2,…,A_n>$。计算乘积，$A_1 A_2 \cdots A_n$。如何让计算尽量快。
- 更快的计算：在这里不考虑对矩阵乘法的专门优化。只考虑一个最优的矩阵乘顺序。即如何添加括号，使得总的乘法计算数量尽量小。
暴力解法：将矩阵乘序列分为两个部分，最后计算两部分的乘积。递归的，暴力进行这种划分方式的搜索。你可以试着推导一下这个的复杂度，简单来说，是指数级别的，$\Omega(2^n)$
思考步骤：
1. 描述最优解结构：对于长度为$l$的矩阵乘序列，$A_i A_{i+1} \cdots A_{i+l} $序列，其最优解包含于$A_i A_{i+1} \cdots A_k \cdot A_{k+1} \cdots A_{i+l}$。遍历$k \in (i,i+l)$，即可获得最优解。
2. 状态转移方程。$f(A,i,i+l) = min_{i<k<i+l-1}\{$ $f(A,i,k)+f(A,k+1,i+l)$ $+ROW(A_i)*COL(A_k)^2*COL(A_{i+l})\}$
3. 自底向上计算：给出边界值，即所有的$l=1$的矩阵乘序列，就是两个矩阵相乘所需要的乘法数量，先算出来这部分。然后分别遍历$l,k$。
4. 最终结果：$f(A,1,n)$
额外的话：
1. 本题的动态规划思路和暴力思路看起来非常相近，但是是有本质区别的。从另一个角度来看，动态规划利用了重叠区间的共享信息。使得最终的时间复杂度达到了$\Theta(n^2)$。

最长公共子序列

描述：
- 两个字符串，形如字符串a：“ABCDEFGXYZ”,字符串b：“AZDZGZXZYZUC”。子序列指的是字符串中部分不重复的字符组成的新字符串，非要形式化的话，对原串$<a_1 a_2 \cdots a_n>$，取序列$1 \le i_1 < i_2 < \cdots < i_{k-1} < i_k \le n$，其中$k \in [0,n]$，则原串的一个子序列为$<a_{i_1} a_{i_2} \cdots a_{i_{k-1}} a_{i_k}>$。
- 最长公共子序列LCS（Longest Common Subsequence）就是求出两个字符串，甚至是多个字符串之间，最长的且相等的子序列。
子串的要求是下标序列$i_1,i_2,\cdots,i_k$必须连续。注意子序列和子串的区分。
暴力解法：枚举二者所有的子序列，从最长的开始比较是否有相等的情况。仅仅是枚举子序列就已经达到$O(2^n)$了哦。
思考步骤：
1. 描述最优子结构：令$f(i,j)$代表第一个字符串$a$包含在范围$<a_1 \cdots a_i>$内的子序列，和第二个字符串$b$包含在范围$<b_1 \cdots b_j>$。
2. 状态转移方程：
  - 如果$a_i = b_j$：则$f(i,j)=f(i-1,j-1)+1$
  - 否则$a_i \ne b_j$：则$f(i,j)=max\{f(i-1,j),f(i,j-1)\}$
3. 自底向上计算：边界情况为$f(1,1)$，分别遍历$i,j$。
4. 最终结果：$f(length(a),length(b))$。
额外的话：
1. 从这里，我们发现，动态规划的状态转移方程，可能有多种情况，不同情况之间的状态转移可能完全不同，有的可能直接算出结果，有的需要进行$min$，$max$等操作。

最优二叉查找树

描述：
- 虽然通过一定的算法，我们能够构造出平衡的二叉搜索树，但是这种搜索树的搜索效率并不是最优的。假设我们需要简单的填鸭式翻译一篇文章，从中文到英文，那么我们希望频率出现最高的词汇，相对的出现在二叉搜索树的顶端，这样能够尽量减少搜索时的访问次数。因此我们需要建立的就是一棵最优二叉搜索树。
- 形式化地，给定一个由$n$个互异的关键字组成的序列$K=<k_1,k_2,\cdots,k_n>$，且关键字有序，即$k_1 < k_2 < \cdots < k_n$。由于某些搜索的值，可能不存在于关键字序列中，因此实际上我们需要使用一套虚拟关键字序列$D=<d_0,d_1,d_2,\cdots,d_n>$，其中$d_0$代表所有小于$k_1$的值，$d_n$代表所有大于$k_n$的值。而对于$d_i \in \{d_1,\cdots,d_{n-1}\}$，虚拟键$d_i$代表所有位于$k_i$，$k_{i+1}$之间的值。使用关键字序列$K$，$D$建立的搜索树中，每个关键字$k_i$是一个内部节点，每个虚拟关键字$d_i$是一个叶子节点。设找到$k_i$的概率为$p_i$，找到$d_i$的概率为$q_i$，显然有$\sum{p_i}+\sum{q_i}=1$。
- 假设搜索代价和节点深度有关，则对于一棵二叉搜索树$T$，一次搜索的期望代价为：$E[T] = \sum_{i=1}^{n}(depth_T(k_i)+1)p_i + \sum_{i=1}^{n}(depth_T(d_i)+1)q_i$
  $= 1 + \sum_{i=1}^{n}depth_T(k_i)p_i + \sum_{i=1}^{n}depth_T(d_i)q_i$
- 如何排列$k_i$使得期望代价最小，就是寻找最优二叉搜索树。
暴力解法：暴力生成所有可能的二叉搜索树的结构，计算搜索期望。这种树的数量是指数级别的，别想了。
思考步骤：
1. 描述最优子结构：
  - 描述一个最优二叉搜索树的最优子结构，没有比子树更合适的描述方式了。任意一个子树必定包含连续范围内的关键字$k_i,\cdots,k_j$，而且此时叶子也恰好为$d_{i-1},\cdots,d_j$。假设此时有一个最优二叉搜索树的子树$T'$，包含$k_i,\cdots,k_j$，那么子树下，取得$k_i,\cdots,k_j$中部分元素的子树（就是子树$T'$的子树）也一定是最优的。（不然就有另一种生成方式了）。
  - 设$f(i,j)$代表关键字$k_i,\cdots,k_j$所生成的树中，具有最小期望代价的情况。
2. 状态转移方程：
  - 当$i=j+1$，$f(i,j)=q_{i-1}$
  - 当$i<j+1$，$f(i,j)=min_{i\le t \le j}\{f(i,t-1)+f(t+1,j)+w(i,j)\}$
    - 其中$w(i,j)=\sum_{t=i}^{j}p_t+\sum_{t=i-1}^{j}q_t$，即该区间上所有的关键字、虚拟关键字的概率总和（深度+1，意味着所有概率都增加一份）
3. 自底向上计算：遍历$i,j$
4. 最终结果：$f(1,n)$
额外的话：在这道题目中，问题的关键在于理解状态转移方程中$i=j+1$的情况。这代表着当前状态存储的是一个单一的虚拟关键字（即叶子节点）。这是本题的边界情况。
- 很多边界情况都考验对最优子结构在边界情况下的理解程度。如果边界理解不正确，常常不能计算出正确的结果。

贪心算法

概述

贪心算法，往往作为一些算法中的策略出现。它的本意就是无脑的选择当前状态下，最优的策略。并且这种最优结果最终，也等价于整体最优。
经常会下意识的进行一些贪心策略的应用。但是需要注意的是，至少要证明一下贪心策略是有效且正确的。
设计思路：
1. 和动态规划类似的：描述最优子结构、设计出一个递归解
2. 证明在递归的任意阶段，只有一个子问题（即只有多种选择中的固定的一种）会保留下来
3. 将递归算法转换为迭代算法

例子

活动选择问题

描述：一个活动表上写着各类活动的安排，这些活动具有起始时间$0 < s_i$，终结时间$e_i$。这些活动之间可能有时间上的重叠。要求计算从起始时刻开始，到某一给定时间$t$为止，能进行的最多的活动数量。
贪心策略：每一次选择在当前时刻之后开始且最早结束的一个活动，并更新当前时刻。

哈夫曼编码

描述：
- 哈夫曼（Huffman）编码是一种经典的数据压缩技术。这里仅针对字符串数据做例子。哈夫曼编码使用一张字符统计表来统计各类字符出现的次数、频率。随后，算法将使用二进制字符编码，将每一个字符，转换为一个固定且唯一的二进制串来表示。比如将字符$a$转换为二进制串$(000)_2$，$b$转换为$(001)_2$。
- 如何进行二进制串的选择，是决定数据压缩效率的关键。采用可变长度的编码显然要优于采用固定长度编码。即对频率高的字符，转换为长度较短的二进制串。（回想一下最优二叉查找树，但是这里不需要考虑搜索失败的情况，编码一定存在）
- 前缀编码（prefix code），即在编码表中，没有任何一个编码，是其他某一个编码的前缀。因此可以唯一的确定
- 哈夫曼编码算法，就是一种产生最优前缀编码的方式。
贪心的构造策略：假设对一个有$n$个字符的字符串构造
- 统计每个字符的频度，
- 用最小优先队列存储节点，节点包含域：字符和它的频度（频度作为优先队列的排序值）
- 每一次出队两个节点，并将它们合并，频率取二者之和，再插回队列（这一步实际在不断创建子树）
- 出队$n-1$次后，最后第$n$次出队，得到最优前缀编码树。
最小优先队列，可以理解为一个最小堆（实际上也往往是这么实现的），每一次出队都会弹出当前队列中最小的值。
哈夫曼编码的使用
- 在得到最优前缀编码树之后，可以将每条路径赋值，一般向左子树的路径分配0，向右子树的分配1。从根节点到达叶子节点（待编码字符）的路径上所依次经过的值，就是它的二进制编码。

扩展阅读：“拟阵”

定义：一个拟阵是满足以下条件的一个序对$M=(S,\mathscr{l})$
1. $S$是一个有穷非空集合
2. $\mathscr{l}$是$S$的一个非空子集族，称为$S$的独立子集，使得如果$B \in \mathscr{l}$且$A \subset B$，那么$A \in \mathscr{l}$。此时也称$\mathscr{l}$是遗传的。注意$\emptyset \in \mathscr{l}$。
3. 如果$A \in \mathscr{l}$，$B \in \mathscr{l}$，且$|A|<|B|$，则有某个元素$x \in B-A$使得$A \cup \{x\} \in \mathscr{l}$。我们称$M$满足交换性质。
用拟阵描述问题的例子：
1. 图的拟阵$M_G=(S_G,\mathscr{l}_G)$，对应无向图$G=(V,E)$
  - 集合$S_G$代表边集$E$
  - 如果$A$是$E$的子集，则$A \in \mathscr{l}_G$当且仅当$A$是无回路的。即子图$G_A=(V,A)$构成一个森林
拟阵和贪心算法的关系：
1. 很多适合用贪心算法的问题，都可以归结为一个加权拟阵问题。即给定一个加权拟阵$M=(S,\mathscr{l})$，求解一个具有最大可能权值$w(A)$的子集$A \in \mathscr{l}$。
拟阵和任务调度问题：
1. 描述：在单核处理器上对若干个消耗单位时间的任务进行最优调度。每一个任务有一个截止期限和超时惩罚。
  - 每个任务只需要单位时间。一个最优调度可以直观的认为就是任务集合的一个全排列。
  - 形式化：包含$n$个单位时间任务的集合$S=\{a_1,a_2,\cdots,a_n\}$。期限$d_1,d_2,\cdots,d_n$，任务$a_i$要求在$d_i$时间之前完成。惩罚值$w_1,w_2,\cdots,w_n$。
  - 求解最小的总惩罚
2. 贪心策略：早开始的任务优先（因为如果超时在前，另一个任务在后，那么显然将超时延后执行也没有坏处）
3. 从拟阵角度思考：
  - 需要做的就是寻找一个可以通过某种调度不产生超时情况的任务的集合$A$。并称这样的任务集合是独立的。
  - 此时的$(S,\mathscr{l})$就构成了一个拟阵。

写在前面

2024年影集

Cpp Concurrency in Action读书笔记

C/C++：内存对象模型

C++ Templates 第二版：读书笔记

Linux：Web和I/O系列书籍读书笔记

Java系列：JVM篇

深入理解Nginx：模块开发与架构解析

《Hadoop权威指南（第四版）》读书笔记

函数式编程：合集