第三章 数学与简单dp

第一节：数学（mathematics）

  1. 找思路

    1. 尽力分析
    2. 打表找规律

裴蜀定理

例题1：买不到的数目

https://www.acwing.com/problem/content/1207/

小明开了一家糖果店。

他别出心裁：把水果糖包成4颗一包和7颗一包的两种。

糖果不能拆包卖。

小朋友来买糖的时候，他就用这两种包装来组合。

当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。

你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。

大于17的任何数字都可以用4和7组合出来。

本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

输入格式

两个正整数 n,m，表示每种包装中糖的颗数。

输出格式

一个正整数，表示最大不能买到的糖数。

数据范围

2≤n,m≤1000
保证数据一定有解。

输入样例：

  1. 4 7

输出样例：

  1. 17

尽力分析：

6和2，他们的gcd（最大公约数）是2，所以他们凑出来的数也一定是2的倍数。如果一个数不是2的倍数，那么就一定凑不出来。所以这输入6和2是无解的（无法找到一个数，大于这个数都能凑出）。

由此可知，如果，存在a和b，若d = gcd(a,b) > 1，则一定不能凑出最大数，即无解情况。

暴力做法：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  7. bool fun(int m, int p, int q) {
  8.     //减到最后，刚好为0，那么返回true
  9.     if (!m)return true;
  10.     //尝试减p
  11.     if (m >= p && fun(m - p, p, q)) return true;
  12.     //尝试减q
  13.     if (m >= q && fun(m - q, p, q)) return true;
  14.     return false;
  15. }
  17. int main() {
  18.     int n, m;
  19.     int res = 0;
  20.     cin >> n >> m;
  21.     for (int i = 1; i <= 2000; i++) {
  22.         if (!fun(i,n,m)) {    //不能买到
  23.             res = i;
  24.         }
  25.     }
  26.     cout << res << endl;
  27.     return 0;
  28. }

打表找规律：

a b c

3 2 1

3 4 5

3 5 7

3 7 11

由此可知b每次增加1，c则增加2，公式为c = 2b - 3;

5 2 3

5 4 11

5 7 23

由此可知b每次增加1，c则增加4，公式为c = 4b - 5

所以公式应该是c = (a - 1) b + x，由于a和b是等同的，所以c = (a - 1)(b - 1) + x

带入一组数，算出x = -1，所以公式为c = (a - 1)(b - 1) - 1

总结1：

给定a，b，若d = gcd(a,b) > 1，则一定不能凑出最大数

总结2：

如果 a,b均是正整数且互质，那么由 ax+by,x≥0,y≥0不能凑出的最大数是 (a−1)(b−1)−1。

代码：

  1. #include <iostream>
  2. using namespace std;
  4. int main() {
  5.     int a, b, c;
  6.     cin >> a >> b;
  7.     c = (a - 1)*(b - 1) - 1;
  8.     cout << c;
  9.     return 0;
  10. }

备注：在比赛中，能用暴力做法做出来就可以了。

例题2：蚂蚁感冒

https://www.acwing.com/problem/content/1213/

长 100 厘米的细长直杆子上有 nn 只蚂蚁。

它们的头有的朝左，有的朝右。

每只蚂蚁都只能沿着杆子向前爬，速度是 1厘米/秒。

当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。

这些蚂蚁中，有 1只蚂蚁感冒了。

并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。

请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。

输入格式

第一行输入一个整数 n, 表示蚂蚁的总数。

接着的一行是 n 个用空格分开的整数 Xi, Xi 的绝对值表示蚂蚁离开杆子左边端点的距离。

正值表示头朝右，负值表示头朝左，数据中不会出现 0 值，也不会出现两只蚂蚁占用同一位置。

其中，第一个数据代表的蚂蚁感冒了。

输出格式

输出1个整数，表示最后感冒蚂蚁的数目。

数据范围

1 0<|Xi|<100

输入样例1：

  1. 3
  2. 5 -2 8

输出样例1：

  1. 1

输入样例2：

  1. 5
  2. -10 8 -20 12 25

输出样例2：

  1. 3

思路：

3数学与简单dp - 图1

C++代码：

  1. /*
  2. 第一个蚂蚁向右走：
  3. 1. 右边向左走，必然被感染
  4. 2. 右边向右走的，必然不会被感染
  5. 3. 左边向左走的，必然不会被感染
  6. 4. 左边向右走的：
  7.     1. 右边存在向左走的，则必然被感染。
  8.     2. 右边不存在向左走的，则必然不会被感染。
  10. 第一个蚂蚁向左走：
  11. 1. 左边向右走的，必然被感染
  12. 2. 左边向左走的，必然不会被感染
  13. 3. 右边向右走的，必然不会被感染
  14. 4. 右边向左走的：
  15.     1. 左边存在向右走的，则必然被感染。
  16.     2. 左边不存在向右走的，则必然不会被感染。
  17. */
  19. #include <cstdio>
  20. #include <cstring>
  21. #include <iostream>
  22. #include <algorithm>
  23. #include <cmath>
  25. using namespace std;
  27. const int N = 60;
  28. int a[N];
  30. int main() {
  31.     int n;
  32.     cin >> n;
  33.     for (int i = 0; i < n; i++) {
  34.         cin >> a[i];
  35.     }
  36.     int left = 0, right = 0; //左边向右走，右边向左走的蚂蚁数量
  37.     for (int i = 1; i < n; i++) {
  38.         if (abs(a[i]) < abs(a[0])) {    //当前蚂蚁是感染蚂蚁的左边
  39.             if (a[i] > 0) left++;    //如果该蚂蚁是向右走，那么左边向右走++
  40.         }
  41.         else {    //当前蚂蚁是感染蚂蚁的右边（不会出现两只蚂蚁占用同一位置）
  42.             if (a[i] < 0) right++;    //如果该蚂蚁是向左走，那么右边向左走++
  43.         }
  44.     }
  45.     if (a[0] > 0 && right == 0 || a[0] < 0 && left == 0) {    //如果向右走，并且右边向左走的为0...
  46.         cout << 1 << endl;    //输出1
  47.     }
  48.     else {
  49.         cout << left + right + 1 << endl;    //输出左边向右走和右边向左走的，以及初始感染者
  50.     }
  51.     return 0;
  52. }

例题3：饮料换购

https://www.acwing.com/problem/content/1218/

乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊C型饮料，凭3个瓶盖可以再换一瓶C型饮料，并且可以一直循环下去(但不允许暂借或赊账)。

请你计算一下，如果小明不浪费瓶盖，尽量地参加活动，那么，对于他初始买入的 n 瓶饮料，最后他一共能喝到多少瓶饮料。

输入格式

输入一个整数 n,表示初始买入的饮料数量。

输出格式

输出一个整数，表示一共能够喝到的饮料数量。

数据范围

0<n<10000

输入样例：

  1. 100

输出样例：

  1. 149

C++代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  7. int main() {
  8.     int n;    //初始饮料个数
  9.     cin >> n;
  11.     int p, g, sum = n;    //瓶，盖，喝过的数量
  12.     g = n;    //得到n个盖
  13.     while (g / 3) {    //如果盖数够换就循环
  14.         p = g / 3;    //换的瓶数
  15.         g = g % 3;    //剩下的盖数
  16.         sum += p;    //瓶数加上去
  17.         g = p + g;    //更新盖数
  18.     }
  19.     cout << sum << endl;
  20.     return 0;
  21. }

第二节 动态规划（Dynamic Programming, DP）

引子：背包问题

01背包问题描述：给我们n个物品，和容量为v的背包，

每个物品有2个参数，一个是它的体积vi，一个是驾驶wi(用w表示权重)

每件物品最多只能用一次。

在这些物品中挑一些物品，这些物品的总体积小于等于背包容量，要使物品的总价值最大，求最大价值。

总结

  1. 01背包问题特点：每件物品最多用一次。（也就是每件物品只有用和不用两种状态，所以谓之01背包问题）

  2. 完全背包问题特点：每件物品有无限个。

  3. 多重背包问题：每个物品的个数不一样，每个物品有Si个。（会讲一个朴素版和优化版）

  4. 分组背包问题：有N组物品，每组有若干个物品，每一组里只能选一个物品。

例题1 01背包问题

https://www.acwing.com/problem/content/2/

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V,用空格隔开，分别表示物品数量和背包容积。

接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 0<vi,wi≤100

输入样例

  1. 4 5
  2. 1 2
  3. 2 4
  4. 3 4
  5. 4 5

输出样例：

  1. 8

分析：

3数学与简单dp - 图2

两维：

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  5. const int N = 1010;
  7. int n, m;    //物品数量、背包容积
  8. int v[N],w[N];    //每个物品的体积和价值
  9. int f[N][N];    //从0~i中选，总体积<=j的最大价值
  11. int main() {
  12.     cin >> n >> m;
  13.     for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
  14.     //免去初始化
  15.     for (int i = 1; i <= n; i++) {
  16.         for (int j = 0; j <= m; j++) {
  17.             f[i][j] = f[i - 1][j];
  18.             if(j >= v[i])f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
  19.         }
  20.     }
  21.     cout << f[n][m] << endl;
  22.     return 0;
  23. }

一维：

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  5. const int N = 1010;
  7. int n, m;    //物品数量、背包容积
  8. int v[N], w[N];
  9. int f[N];    //总体积<=j的最大价值
  11. int main() {
  12.     cin >> n >> m;
  13.     for (int i = 1; i <= n; i++) {
  14.         cin >> v[i] >> w[i];
  15.         for (int j = m; j >= v[i]; j--) {
  16.             f[j] = max(f[j], f[j - v[i]] + w[i]);
  17.         }
  18.     }
  19.     cout << f[m] << endl;
  20.     return 0;
  21. }

再优化：

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  5. const int N = 1010;
  7. int n, m;    //物品数量、背包容积
  8. int f[N];    //总体积<=j的最大价值
  10. int main() {
  11.     cin >> n >> m;
  12.     for (int i = 0; i < n; i++) {
  13.         int v, w;    //物品的体积、价值
  14.         cin >> v >> w;
  15.         for (int j = m; j >= v; j--) {
  16.             f[j] = max(f[j], f[j - v] + w);
  17.         }
  18.     }
  19.     cout << f[m] << endl;
  20.     return 0;
  21. }

例题2：摘花生

https://www.acwing.com/problem/content/1017/

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

3数学与简单dp - 图3

输入格式

第一行是一个整数T，代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式

对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。

数据范围

1≤T≤100
1≤R,C≤100
0≤M≤1000

输入样例：

  1. 2
  2. 2 2
  3. 1 1
  4. 3 4
  5. 2 3
  6. 2 3 4
  7. 1 6 5

输出样例：

  1. 8
  2. 16

思路：

3数学与简单dp - 图4

C++代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  7. const int N = 110;
  8. int w[N][N];    //记录花生数
  9. int f[N][N];    //状态表示：从(1,1)到(i，j)的所有路线中花生数最多的。
  11. int main() {
  12.     int T;
  13.     cin >> T;
  14.     while (T--) {
  15.         int R, C;
  16.         scanf("%d%d", &R, &C);
  17.         for (int i = 1; i <= R; i++) {
  18.             for (int j = 1; j <= C; j++) {
  19.                 scanf("%d", &w[i][j]);
  20.                 f[i][j] = max(f[i - 1][j],f[i][j - 1]) + w[i][j];
  21.             }
  22.         }
  23.         cout << f[R][C] << endl;
  24.     }
  25.     return 0;
  26. }

例题3：最长上升子序列

https://www.acwing.com/problem/content/897/

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数N。

第二行包含N个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤1000
−10^9 ≤数列中的数≤10^9

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

思路：

3数学与简单dp - 图5

C++代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int n;
int a[N];
int f[N];

int main() {
    cin >> n;
    for(int i = 1; i<=n; i++) scanf("%d", &a[i]);
    int res = 0;
    for (int i = 1; i <= n; i++) {

        f[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                f[i] = max(f[j] + 1, f[i]);
            }

        }
        res = max(res, f[i]);
    }
    cout << res << endl;
    return 0;
}

作业1：地宫取宝

https://www.acwing.com/problem/content/1214/

X 国王有一个地宫宝库，是 n×m 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是 k 件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k 件宝贝。

输入格式

第一行 3 个整数，n,m,k，含义见题目描述。

接下来 n行，每行有 m个整数 Ci用来描述宝库矩阵每个格子的宝贝价值。

输出格式

输出一个整数，表示正好取 k个宝贝的行动方案数。

该数字可能很大，输出它对 1000000007取模的结果。

数据范围

1≤n,m≤50
1≤k≤12
0≤Ci≤12

输入样例1：

2 2 2
1 2
2 1

输出样例1：

2

输入样例2：

2 3 2
1 2 3
2 1 5

输出样例2：

14

C++代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 60,MOD = 1000000007;
int n, m, k;    //地图大小，目标宝贝数
int w[N][N];    //存每个格子宝贝价值
int f[N][N][20][20];    //四维状态

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> w[i][j];
            w[i][j] ++;
        }
    }
    //初始化
    f[1][1][1][w[1][1]] = 1;
    f[1][1][0][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1)continue;
            for (int u = 0; u <= k; u++) {    //已经取了u件物品
                for (int v = 0; v <= 13; v++) {    //最后一件物品的价值为v
                    int &val = f[i][j][u][v];
                    val = (val + f[i - 1][j][u][v]) % MOD;
                    val = (val + f[i][j - 1][u][v]) % MOD;
                    if (u > 0 && v == w[i][j]) {
                        for (int c = 0; c < v; c++) {    //倒数第二件物品的价值为w
                            val = (val + f[i - 1][j][u - 1][c]) % MOD;
                            val = (val + f[i][j - 1][u - 1][c]) % MOD;
                        }
                    }
                }
            }
        }
    }
    int res = 0;
    for (int i = 0; i <= 13; i++) {
        res = (res + f[n][m][k][i]) % MOD;
    }
    cout << res << endl;

    return 0;
}

作业2：波动数列

https://www.acwing.com/problem/content/1216/

观察这个数列：

1 3 0 2 -1 1 -2 …

这个数列中后一项总是比前一项增加2或者减少3，且每一项都为整数。

栋栋对这种数列很好奇，他想知道长度为 n和为 s而且后一项总是比前一项增加 a或者减少 b的整数数列可能有多少种呢？

输入格式

共一行，包含四个整数 n,s,a,b含义如前面所述。

输出格式

共一行，包含一个整数，表示满足条件的方案数。

由于这个数很大，请输出方案数除以 100000007的余数。

数据范围

1≤n≤1000
−10^9 ≤ s ≤ 10^9
1≤a,b≤ 10^6

输入样例：

4 10 2 3

输出样例：

2

样例解释

两个满足条件的数列分别是2 4 1 3和7 4 1 -2。

C++代码：

/*
动态规划：
状态表示：f[i][j]    :前i项的总和%n == j的方案的数量
状态计算：
f[i][j] = f[i-1][(j-i*a)%n] + f[i-1][(j+i*b)%n]
初始化：
f[0][0] = 1
*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010,MOD = 100000007;

int f[N][N];

int get_mod(int a,int b) {    // 求a除以b的正余数
    return (a % b + b) % b;
}

int main() {
    int n, s, a, b;    //长度为n，和为s，后一项总比前一项增加a或减少b的整数数列可能有多少种？
    cin >> n >> s >> a >> b;

    f[0][0] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            f[i][j] = (f[i - 1][get_mod(j - i * a,n)] + f[i - 1][get_mod(j + i * b, n)]) % MOD;
        }
    }
    cout << f[n - 1][get_mod(s,n)] << endl;
    return 0;
}