暑假集训第六篇周记（8月14号-8月20号）

岁杪二四...大约 10 分钟

摘要

涉及内容： 动态规划、数论

每日知识点

第一天 8月14日：动态规划(Dynamic Programming, DP)

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

一些问题具有两个特征：重叠子结构、最优子结构。用 $DP$ 可以高效率地处理具有这两个特征的问题

重叠子结构
首先，子问题是原大问题的小版本，计算步骤完全一样；其次，计算大问题时，需要多次重复计算小问题，这就是重叠子问题。一个子问题的多次重复计算，耗费了大量的时间。用 $DP$ 处理重叠子问题，每个问题只计算一次，从而避免了重复计算，这就是 $DP$ 高效率的原因。具体的做法是首先分析得到最优子结构，然后用递推或者带记忆化搜索的递归进行编程，从而实现高效的计算。
最优子结构
首先，大问题的最优解包含小问题的最优解；其次，可以通过小问题的最优解推到出大问题的最优解，这就是最优子结构。
无后效性
“未来与过去无关”只关心前面的结果，不关心前面的过程，在计算第 $i$ 项时直接使用第 $i-1$ 项的结果，不需要知道它们的计算过程这就是无后效性。无后效性是应用 $DP$ 的必要条件

基本思路

对于一个能用动态规划解决的问题，一般采用如下思路解决：

将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为状态）；
寻找每一个状态的可能决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程 ）。
按顺序求解每一个阶段的问题。

第二天 8月15日：动态规划最长公共子序列LCS和最长上升子序列LIS

最长公共子序列LCS

给定一个长度为 $n$ 的序列 $A$ 和一个长度 $m$ 的序列 $B(n,m≤5000)$ ,求出一个最长的序列，使得该序列既是 $A$ 的子序列，又是 $B$ 的子序列。

设 $f(i,j)$ 表示只考虑 $A$ 的前 $i$ 个元素， $B$ 的前 $j$ 个元素时的最长公共子序列的长度，求这时的最长公共子序列的长度就是子问题。 $f(i,j)$ 就是我们所说的状态，则 $f(n,m)$ 是最终要达到的状态，即为所求结果。

对于每个 $f(i,j)$ ，存在三种决策：如果 $A_i = B_j$ ，则可以将她们接到公共子序列的末尾；另外两种决策分别是跳过 $A_i$ 或者是 $B_j$ 。状态转移方程如下：

f(i,j)=\begin{cases} f(i-1,j-1)+1, & A_i = B_j \\ \max(f(i-1,j),f(i,j-1)) & A_i\neq B_j \end{cases}

int a[MAXN], b[MAXM], f[MAXN][MAXM];

int dp() {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (a[i] == b[j])
        f[i][j] = f[i - 1][j - 1] + 1;
      else
        f[i][j] = std::max(f[i - 1][j], f[i][j - 1]);
  return f[n][m];
}

最长上升子序列LIS

给定一个长度为 $n$ 的序列 $A(n≤5000)$ ，求出一个最长的 $A$ 的子序列，满足该子序列的后一个元素不小于前一个元素

设 $f(i)$ 表示以 $A_i$ 为结尾的最长不下降子序列的长度，则所求为 $max_{1 \leq i \leq n} f(i)$

计算 $f(i)$ 时，尝试将 $A_i$ 接到其他的最长不下降子序列后面，以更新答案。于是可以写出这样的状态转移方程：

f(i) = max_{1\leq j<i,A_j\leq A_i}(f(j)+1)

int a[MAXN], d[MAXN];

int dp() {
  d[1] = 1;
  int ans = 1;
  for (int i = 2; i <= n; i++) {
    d[i] = 1;
    for (int j = 1; j < i; j++)
      if (a[j] <= a[i]) {
        d[i] = max(d[i], d[j] + 1);
        ans = max(ans, d[i]);
      }
  }
  return ans;
}

第三天 8月16日：动态规划背包问题

$01$ 背包

「USACO07 DEC」Charm Braceletopen in new window
题意概要：有 $n$ 个物品和一个容量为 $W$ 的背包，每个物品有重量 $w_i$ 和价值 $v_i$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量

在这道题中，由于每个物品只有两种可能的状态（取或者不取），对应二进制中的 $0$ 和 $1$ ，这类问题便被称为 $01$ 背包问题

设 $DP$ 状态 $f_{i,j}$ 为只能放前 $i$ 个物品的情况下，容量为 $j$ 的背包所能达到的最大总价值

考虑转移。假设当前已经处理好了前 $i-1$ 个物品的所有状态，那么对于第 $i$ 个物品，当其不放入背包时，背包的剩余容量不变，背包中的物品的总价值也不变，故这种情况的最大价值为 $f_{i-1,j-w_i}+v_i$

由此可以得出状态转移方程：

f_{i,j}=max(f_{i-1,j},f_{i-1,j-w_i}+v_i)

由于对 $f_i$ 影响的只有 $f_{i-1}$ ，可以去掉第一维，直接用 $f_i$ 来表示处理到当前物品时背包的容量为 $i$ 的最大价值，得出以下方程：

f_j=max(f_j,f_{j-w_i}+v_i)

务必牢记并理解这个状态转移方程，因为大部分背包问题的转移方程都是在此基础上推导出来的

#include <iostream>
using namespace std;
const int maxn = 13010;
int n, W, w[maxn], v[maxn], f[maxn];

int main() {
  cin >> n >> W;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];  // 读入数据
  for (int i = 1; i <= n; i++)
    for (int l = W; l >= w[i]; l--)
      if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l - w[i]] + v[i];  // 状态方程
  cout << f[W];
  return 0;
}

完全背包

完全背包模型与 $01$ 背包类似，与 $01$ 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

状态定义：设 $f_{i,j}$ 为只能选前 $i$ 个物品时，容量为 $j$ 的背包可以达到的最大价值。

考虑一个简单的做法：对于第 $i$ 件物品，枚举其选了多少个来转移。这样做的时间复杂度是 $O(n^3)$ 的

状态转移方程如下：

f_{i,j} = \max_{k = 0}^{+\infty} (f_{i-1,j-k\times w_i}+v_i\times k)

考虑做一个简单的优化。可以发现，对于 $f_{i,j}$ ，只要通过 $f_{i,j-w_i}$ 转移就可以了。因此状态方程为：

f_{i,j} = max(f_{i-1,j},f_{i,j-w_i}+v_i)

多重背包

多重背包也是 $01$ 背包的一个变式。与 $01$ 背包的区别在于每个物品有 $k_i$ 个，而非一个。

把每个物品选 $k_i$ 次等价转化为有 $k_i$ 个相同的物品，每个物品选一次，这样就转换成了一个 $01$ 背包模型。状态转移方程如下：

f_{i,j} = \max_{k = 0}^{k_i} (f_{i-1,j-k\times w_i}+v_i\times k)

混合背包

混合背包就是将前面的三种背包问题混合起来，有的只能取一次，有的能取无限次，有的只能取 $k$ 次。

以下是伪代码：

for (循环物品种类) {
  if (是 0 - 1 背包)
    套用 0 - 1 背包代码;
  else if (是完全背包)
    套用完全背包代码;
  else if (是多重背包)
    套用多重背包代码;
}

分组背包

分组背包，就是将物品分组，每组的物品相互冲突，最多只能选一个物品放进去。

怎么想呢？就是从在所有的物品中选一件变成了从当前组中选择一件，对每一组进行一次 $01$ 背包就好了

for (int k = 1; k <= ts; k++)          // 循环每一组
  for (int i = m; i >= 0; i--)         // 循环背包容量
    for (int j = 1; j <= cnt[k]; j++)  // 循环该组的每一个物品
      if (i >= w[t[k][j]])
        dp[i] = max(dp[i],
                    dp[i - w[t[k][j]]] + c[t[k][j]]);  // 像0-1背包一样状态转移

一定不能搞错循环顺序

第四天 8月17日：动态规划综合问题

内容结合前三天

第五天 8月17日：数论 (模运算、快速幂、GCD、LCM、扩展欧几里得)

模运算

一个数太大，无法直接输出，或者不需要直接输出，那么可以把它取模，缩小数值再输出
模运算：a mod m = a % m

取模的应用

处理循环节

1 4 2 8 5 7 1 4 2 8 5 7 1 4 2 8 5 7 ...

已知循环节长度为 $6$ ，那么第 $n$ 位的数字就是 $a[(n-1)\%6+1]$

同余

小明和小刚是两个好朋友，他们在上体育课时排成一排，分别在位置a和位置b，体育老师让他们分别以1 - n 轮流报数，然后报到数字相同的，出列为一组。假如你可以操作体育老师给定的数字n，你要如何确定一个数字n能让小明和小刚为一组呢？

此题本质就是一个求模数 $n$ ，使得 $a$ 和 $b$ 在对 $n$ 取模下是相等的，答案就是 $b-a$

引入同余定理：若 $(a-b) \quad mod \quad p =0$ 则 $a \quad mod \quad p = b \quad mod \quad p$

假设 $a \quad mod \quad p=b \quad mod \quad p$

可设 $a = p*k+d$

可设 $b = p*t+d$

则 $(a-b) \quad mod \quad p= (p*(k+t)+d-d)mod \quad p=0$

取模公式

加法： $(a+b)\%p = ((a\%p)+(b\%p))\%p$

减法： $(a-b)\%p = ((a\%p)-(b\%p))\%p$

乘法： $(a*b)\%p = ((a\%p)*(b\%p))\%p$

除法这样做是错的，除法的取模需要用到逆元

快速幂

当计算某些大数时，无法直接计算或者能计算但是运行超时，采用快速幂进行计算

例如算 $a^{11}$ ： $a^{11}=a^{8+2+1}=a^8 \times a^2 \times a^1$ ，其中 $a^8$ 、 $a^2$ 、 $a^1$ 是倍乘关系，分解采用二进制分解， $11_{10}=1011_2=2^3+2^1+2^0=8+2+1$

从低位往高位处理 $1011_2$ (右移一次，就把刚处理的低位移走了)

int fastPow(int a, int n, int mod){
    int base = a;
    int res = 1;
    while(n){
        if(n & 1)   //如果n的最后一位是1，表示这个地方需要乘
              res *= base % mod;
        base *= base % mod;    //推算乘积，a2-->a4-->a8-->a16...
        n >>= 1;       //n右移一位，把刚处理过的n的最后一位去掉
    }
    return res;
}

矩阵快速幂

给定一个 $m \times m$ 的矩阵A，求他的 $n$ 次幂 $A^n$ 。

定义矩阵的结构体

const int MAXN = 2;    //定义矩阵的阶；本例子是2
const int MOD = 1e4;   //根据题目要求定义模

struct Matrix{         //定义矩阵
     int m[MAXN][MAXN];
     Matrix(){
          memset(m,0,sizeof(m));
     }
};

定义矩阵的乘法

Matrix Multi(Matrix a, Matrix b){   //矩阵的乘法
     Matrix res;
     for(int i=0; i<MAXN; i++)
         for(int j=0; j<MAXN; j++)
             for(int k=0; k<MAXN; k++)
                  res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
      return res;
}

定义矩阵的快速幂

Matrix fastm(Matrix a, int n){
    Matrix res;
    for(int i=0; i<MAXN; i++)  //初始化为单位矩阵，相当于前面程序的int res = 1;
    res.m[i][i] = 1;
    while(n){
          if(n&1)    res = Multi(res,a);
          a = Multi(a,a);
          n >>=  1;
    }
    return res;
}

GCD和LCM

昵称

邮箱

网址

按正序
按倒序
按热度