AcWing-算法提高课（第一章）-下

本文主要是介绍AcWing-算法提高课（第一章）-下，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

区间DP

环形石子合并

状态表示：f[i,j]（f[i,j]表示，在，由，将第i堆石子到第j堆石子合并成一堆石子的每个合并方式的代价，组成的集合，中，的最小值）
状态计算：f[i,j]=min(f[i,k]+f[k+1,j]+s[j]-s[i-1])（s[j]表示第1堆石子到第j堆石子的总重量，s[i-1]表示第1堆石子到第i-1堆石子的总重量，s[j]-s[i-1]表示第i堆石子到第j堆石子的总重量，k∈{i,i+1,i+2,…,j-1}）

环形石子合并

#include <iostream>
#include <cstring>using namespace std;const int N = 400 + 10;int n;
int f[N][N];// 状态表示，计算最小值
int g[N][N];// 状态表示，计算最大值
int w[N];// 存储每堆石子的重量
int s[N];// 前缀和数组int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++){scanf("%d", &w[i]);w[i + n] = w[i];// 通过这样的操作，即可把环形石子问题，转化为线性石子问题}for (int i = 1; i <= 2 * n; i++)s[i] = s[i -  1]  + w[i];// 前缀和memset(f, 0x3f, sizeof f);memset(g, -0x3f, sizeof g);// 按区间长度从小到大进行遍历for (int len = 1; len <= n; len++)// 区间长度从1开始// 遍历当前区间长度的左边界for (int l = 1; l + len - 1 <= 2 * n; l++){int r = l + len - 1;// 右边界if (len == 1)f[l][r] = g[l][r] = 0;else// 状态计算for (int k = l; k < r; k++){f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);}}int min_res = 0x3f3f3f3f;int max_res = -0x3f3f3f3f;for (int i = 1; i <= n + 1; i++){min_res = min(min_res, f[i][i + n - 1]);max_res = max(max_res, g[i][i + n - 1]);}// 输出结果printf("%d\n%d\n", min_res, max_res);return 0;
}

能量项链

状态表示：f[i,j]（f[i,j]表示，在，由，将下标为i到下标为j-1的所有珠子合并成一颗珠子的每个合并方式所释放的能量，组成的集合，中，的最大值）
*状态计算：f[i,j]=max(f[i,k]+f[k,j]+w[i]*w[k]w[j])（w[i]表示下标为i的珠子的头标记，w[k]表示下标为k的珠子的头标记，w[j]表示下标为j-1的珠子的尾标记，k∈{i+1,i+2,…,j-1}）

能量项链

#include <iostream>using namespace std;const int N = 200 + 10;int n;
int f[N][N];// 状态表示
int w[N];int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++){scanf("%d", &w[i]);w[i + n] = w[i];// 通过这样的操作，即可把环形问题，转化为线性问题}w[2 * n + 1] = w[1];// 加上这一行是为了和解题的思路更加吻合// 按区间长度从小到大进行遍历// 区间长度从3开始，是因为至少要有两颗能量珠才能进行合并，才有意义// 注意，这里的区间长度的上限为n+1for (int len = 3; len <= n + 1; len++)// 遍历当前区间长度的左边界for (int l = 1; l + len - 1 <= 2 * n + 1; l++){int r = l + len - 1;// 右边界// 状态计算for (int k = l + 1; k < r; k++)f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);}int res = 0;for (int i = 1; i <= n + 1; i++)res = max(res, f[i][i + n]);// 从i到i+n的长度为n+1// 输出结果    printf("%d\n", res);return 0;
}

凸多边形的划分

状态表示：f[L,R]（f[L,R]表示，在，由，把由(L,L+1)，(L+1,L+2)，(L+2,L+3)，…，(R-2,R-1)，(R-1,R)，(R,L)这些边所构成的凸多边形划分成若干个互不相交的三角形的每个划分方式的所有三角形的顶点权值乘积之和，组成的集合，中，的最小值）
*状态计算：f[L,R]=min(f[L,K]+f[K,R]+w[L]*w[K]w[R])（w[K]表示下标为K的结点的权值，K∈{L+1,L+2,…,R-1}）

凸多边形的划分

#include <iostream>
#include <cstring>using namespace std;typedef long long LL;const int N = 55;
const int M = 35;// 最终的十进制表示的值，长度不会超过35位int n;
int w[N];// 存储每个结点的权值
LL f[N][N][M];// 数组的前两维用于状态表示，数组的第三维用于存储当前状态表示的（高精度）值void mul(LL a[], int b)// 高精度乘法
{LL res[M];memset(res, 0, sizeof res);// 局部变量要赋值，否则存储的是随机值，会影响计算LL t = 0;for (int i = 0; i < M; i++){t = a[i] * b + t;res[i] = t % 10;t = t / 10;}memcpy(a, res, sizeof res);
}void add(LL a[], LL b[])// 高精度加法
{LL res[M];memset(res, 0, sizeof res);// 局部变量要赋值，否则存储的是随机值，会影响计算LL t = 0;for (int i = 0; i < M; i++){t = a[i] + b[i] + t;res[i] = t % 10;t = t / 10;}memcpy(a, res, sizeof res);
}int cmp(LL a[], LL b[])// 高精度比较大小
{for (int i = M - 1; i >= 0; i--)if (a[i] > b[i])return 1;else if (a[i] < b[i])return -1;return 0;
}void res_printf(LL a[])// 高精度打印输出
{int k = M - 1;// 前置0不打印输出while (k && !a[k])k--;for (int i = k; i >= 0; i--)printf("%lld", a[i]);printf("\n");
}/*通过这个题目，再次学习了以下知识点：1、在C++中，数组作为参数传递给函数时，是引用类型的参数传递2、在C++中，当你使用memcpy函数复制long long类型的数据时，它会按照字节的顺序进行复制，对于每一位字节，会先复制低位字节，然后再复制高位字节3、在C++中，如果两个int类型的整数相乘的结果会溢出，则要先把int类型的整数改成long long类型，然后再进行相乘4、在C++的条件表达式中，除了0以外的所有整数都视为true
*/
int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &w[i]);// 按区间长度从小到大进行遍历// 区间长度从3开始，是因为至少要有三个结点才能构成一个三角形，才有意义for (int len = 3; len <= n; len++)// 遍历当前区间长度的左边界for (int l = 1; l + len - 1 <= n; l++){int r = l + len - 1;// 右边界// 表示当前状态表示的（高精度）值为：10000 00000 00000 00000 00000 00000 00000，相当于正无穷f[l][r][M - 1] = 1;// 状态计算for (int k = l + 1; k < r; k++){LL temp[M];memset(temp, 0, sizeof temp);// 局部变量要赋值，否则存储的是随机值，会影响计算temp[0] = w[l];// 状态计算：f[L,R]=min(f[L,K]+f[K,R]+w[L]*w[K]*w[R])mul(temp, w[k]);mul(temp, w[r]);add(temp, f[l][k]);add(temp, f[k][r]);if (cmp(f[l][r], temp) > 0)memcpy(f[l][r], temp, sizeof temp);}}// 输出结果    res_printf(f[1][n]);return 0;
}

加分二叉树

状态表示：f[L,R]（f[L,R]表示，在，由，中序遍历符合L,L+1,L+2,…,R-2,R-1,R的每个二叉树的加分，组成的集合，中，的最大值）
*状态计算：f[L,R]=max(f[L,K-1]f[K+1,R]+w[K])（w[K]表示当前以K为根节点的二叉树的根节点的分数，K∈{L,L+1,L+2,…,R-2,R-1,R}）

加分二叉树

#include <iostream>using namespace std;const int N = 30 + 10;int n;
int w[N];
int f[N][N];// 状态表示
int g[N][N];// 记录当前二叉树的根节点void dfs(int l, int r)// 递归输出最终求得的二叉树的前序遍历（根节点--->左节点--->右节点）
{if (r < l)return;int k = g[l][r];printf("%d ", k);dfs(l, k - 1);dfs(k + 1, r);
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &w[i]);// 按区间长度从小到大进行遍历for (int len = 1; len <= n; len++)// 遍历当前区间长度的左边界for (int l = 1; l + len - 1 <= n; l++){int r = l + len - 1;// 右边界if (len == 1){f[l][r] = w[l];g[l][r] = l;// 记录当前二叉树的根节点}else{// 状态计算for (int k = l; k <= r; k++){// 若k为左端点，则当前以k为根节点的二叉树的左子树的加分为1int left = k == l ? 1 : f[l][k - 1];// 若k为右端点，则当前以k为根节点的二叉树的右子树的加分为1int right = k == r ? 1 : f[k + 1][r];if (f[l][r] < left * right + w[k])// 因为要输出字典序最小的方案，所以这里不能用<=，只能用<{f[l][r] = left * right + w[k];g[l][r] = k;// 记录当前二叉树的根节点}}}}printf("%d\n", f[1][n]);// 输出结果dfs(1, n);// 递归输出最终求得的二叉树的前序遍历（根节点--->左节点--->右节点）return 0;
}

棋盘分割

状态表示：f[x1,y1,x2,y2,k]（f[x1,y1,x2,y2,k]表示，在，由，将左上角为(x1,y1)和右下角为(x2,y2)的矩形棋盘分割成k块矩形棋盘的每个分割方式的均方差，组成的集合，中，的最小值）
状态计算：
- 枚举横着切的情况
  - f[x1,y1,x2,y2,k]=min(get(x1,y1,i,y2)+dp(i+1,y1,x2,y2,k-1))（get(x1,y1,i,y2)表示拿走上方的矩形棋盘，dp(i+1,y1,x2,y2,k-1)表示继续递归处理下方的矩形棋盘，其中i∈{x1,x1+1,…,x2-1}）
  - f[x1,y1,x2,y2,k]=min(get(i+1,y1,x2,y2)+dp(x1,y1,i,y2,k-1))（get(i+1,y1,x2,y2)表示拿走下方的矩形棋盘，dp(x1,y1,i,y2,k-1)表示继续递归处理上方的矩形棋盘，其中i∈{x1,x1+1,…,x2-1}）
- 枚举竖着切的情况
  - f[x1,y1,x2,y2,k]=min(get(x1,y1,x2,j)+dp(x1,j+1,x2,y2,k-1))（get(x1,y1,x2,j)表示拿走左方的矩形棋盘，dp(x1,j+1,x2,y2,k-1)表示继续递归处理右方的矩形棋盘，其中j∈{y1,y1+1,…,y2-1}）
  - f[x1,y1,x2,y2,k]=min(get(x1, j+1,x2,y2)+dp(x1,y1,x2,j,k-1))（get(x1, j+1,x2,y2)表示拿走右方的矩形棋盘，dp(x1,y1,x2,j,k-1)表示继续递归处理左方的矩形棋盘，其中j∈{y1,y1+1,…,y2-1}）

棋盘分割

#include <iostream>
#include <cstring>
#include <cmath>using namespace std;const int K = 15;int k;
int s[9][9];// 这是一个8*8的矩形棋盘
double f[9][9][9][9][K];// 状态表示
double k_average;// 根据题意，得到均方差
double get(int x1, int y1, int x2, int y2)
{double sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] - k_average;return sum * sum / k;
}double dp(int x1, int y1, int x2, int y2, int k)
{double &t = f[x1][y1][x2][y2][k];// 当一个变量名太长时，可以通过这种方式给变量名起个别名，变量的类型要保持一致// 当f[x1][y1][x2][y2][k]不等于-1时，则表明已经计算过f[x1][y1][x2][y2][k]的最小值，无需再进行计算，减少程序运行时间if (t != -1)return t;if (k == 1)return get(x1, y1, x2, y2);t = 0x3f3f3f3f;// 把f[x1][y1][x2][y2][k]初始化为一个很大的值，是为了求f[x1][y1][x2][y2][k]的最小值for (int i = x1; i < x2; i++)// 枚举横着切的情况{// 拿走上方的矩形棋盘，继续递归处理下方的矩形棋盘t = min(t, get(x1, y1, i, y2) + dp(i + 1, y1, x2, y2, k - 1));// 拿走下方的矩形棋盘，继续递归处理上方的矩形棋盘t = min(t, get(i + 1, y1, x2, y2) + dp(x1, y1, i, y2, k - 1));}for (int j = y1; j < y2; j++)// 枚举竖着切的情况{// 拿走左方的矩形棋盘，继续递归处理右方的矩形棋盘t = min(t, get(x1, y1, x2, j) + dp(x1, j + 1, x2, y2, k - 1));// 拿走右方的矩形棋盘，继续递归处理左方的矩形棋盘t = min(t, get(x1, j + 1, x2, y2) + dp(x1, y1, x2, j, k - 1));}return t;
}/*通过这个题目，再次学习了以下知识点：1、double类型在计算机中是通过IEEE754标准来存储的，这是一种用于浮点数表示的标准，IEEE754标准定义了浮点数的存储格式、数值范围和精度，在IEEE754标准中，一个double类型的浮点数占用64位（8字节）内存空间，其中：第1位是符号位（0表示正数，1表示负数）接下来的11位是指数部分最后的52位是尾数（也称为有效数字）2、使用memset函数来初始化double类型的数组是不正确的做法，正确的做法是使用循环来遍历数组并设置每个元素的值
*/
int main()
{scanf("%d", &k);// 把8*8的矩形棋盘，分割成k块矩形棋盘for (int i = 1; i <= 8; i++)for (int j = 1; j <= 8; j++){scanf("%d", &s[i][j]);// 二维前缀和s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];}// 根据题意，得到平均值k_average = (double)s[8][8] / k;// 注意，两个整数相除，结果为整数，需要手动转成浮点数// 使用memset函数来初始化double类型的数组是不正确的做法，正确的做法是使用循环来遍历数组并设置每个元素的值for (int i = 1; i <= 8; i++)for (int j = 1; j <= 8; j++)for (int a = 1; a <= 8; a++)for (int b = 1; b <= 8; b++)for (int v = 1; v <= k; v++)f[i][j][a][b][v] = -1;// 用于记忆化搜索printf("%.3lf\n", sqrt(dp(1, 1, 8, 8, k)));// 采用记忆化搜索的方式，解决DP问题return 0;
}

树形DP

树的一条直径：树中边的权值之和最大的一条路径

给定一棵边的权值为1的树，然后找出树的一条直径：
- 1、任取一结点作为起点，找到距离该结点最远的一个结点u
- 2、再找到距离结点u最远的一个结点v
- 3、那么u和v之间的路径就是这颗树的一条直径
给定一棵边的权值可能存在负数的树，然后找出树的一条直径，此时，就需要用到树形DP来解决

树的最长路径

#include <iostream>
#include <cstring>using namespace std;const int N = 1e4 + 10;
const int M = N * 2;int n;
int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int w[M];// 存储第idx条边的权值
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条
int ans;// 存储树的一条直径的长度void add(int a, int b, int c)// 插入一条a节点指向b节点的边，c为边的权值
{w[idx] = c;e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}int dfs(int u, int father)// father为u节点的父节点
{int dist = 0;// 存储从u节点出发，一直往下走所能经过的第一长的路径的长度int d1 = 0;// 存储从u节点出发，一直往下走所能经过的第一长的路径的长度int d2 = 0;// 存储从u节点出发，一直往下走所能经过的第二长的路径的长度// 遍历u节点的所有出边for (int i = h[u]; i != -1; i = ne[i]){// 因为此图为无向图，加上此判断，是为了防止在dfs操作的过程中发生死循环if (e[i] == father)continue;// 递归进行dfs操作，w[i]为u节点和其当前子节点的边的权值int t = dfs(e[i], u) + w[i];dist = max(dist, t);// 存储从u节点出发，一直往下走所能经过的第一长的路径的长度if (t > d1)// 更新从u节点出发，一直往下走所能经过的第一长和第二长的路径的长度{d2 = d1;d1 = t;}else if (t > d2)// 更新从u节点出发，一直往下走所能经过的第二长的路径的长度d2 = t;}ans = max(ans, d1 + d2);return dist;
}// 注意：当这棵树的所有边的权值全为负数时，此时只选一个点，不选边，树的一条直径的长度为0
int main()
{scanf("%d", &n);// 初始化每个节点对应的单链表的表头所指向的idx为-1，表示每个节点与其它节点都不直接相连memset(h, -1, sizeof h);for (int i = 1; i <= n - 1; i++){int a, b, c;scanf("%d %d %d", &a, &b, &c);// 无向图add(a, b, c);add(b, a, c);}/*先随便找一个节点作为整棵树的根节点（这个根节点也是dfs操作的起点），然后按照整棵树的高度依次往下，每个节点（包括根节点）都可以视为是树中的某些路径所经过的所有节点中高度最高的节点，据此，即可把树中的所有路径按照节点进行分类，通过dfs操作，枚举每一个节点，相当于枚举树中的所有路径，最终可以找到树的一条直径的长度*/// 把第一个节点作为整棵树的根节点，根节点的父节点视为无，可设置成一个无效值-1，然后开始进行dfs操作dfs(1, -1);printf("%d\n", ans);return 0;
}

树的中心：在树中找到一个节点，使得该节点到树中其它节点的最大值是其余节点到树中其它节点的最大值中的最小值，那么这个节点被称为树的中心

树的中心

#include <iostream>
#include <cstring>using namespace std;const int N = 1e4 + 10;
const int M = N * 2;int n;
int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int w[M];// 存储第idx条边的权值
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条
int d1[N];// 存储从u节点出发，一直往下走所能经过的第一长的路径的长度
int d2[N];// 存储从u节点出发，一直往下走所能经过的第二长的路径的长度
int p1[N];// 存储从u节点出发，一直往下走所能经过的第一长的路径对应所经过的子节点的编号
int u1[N];// 存储从u节点出发，先往上走所能经过的第一长的路径的长度
bool is_leaf[N];// 存储u节点是否为无法再继续往下走的节点void add(int a, int b, int c)// 插入一条a节点指向b节点的边，c为边的权值
{w[idx] = c;e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}int dfs_d(int u, int father)// father为u节点的父节点
{d1[u] = d2[u] = -0x3f3f3f3f;// 遍历u节点的所有出边for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];// 因为此图为无向图，加上此判断，是为了防止在dfs操作的过程中发生死循环if (j == father)continue;// 递归进行dfs操作，w[i]为u节点和其当前子节点的边的权值int t = dfs_d(j, u) + w[i];if (t > d1[u]){// 更新从u节点出发，一直往下走所能经过的第一长和第二长的路径的长度d2[u] = d1[u];d1[u] = t;// 更新从u节点出发，一直往下走所能经过的第一长的路径对应所经过的子节点的编号p1[u] = j;}else if (t > d2[u])// 更新从u节点出发，一直往下走所能经过的第二长的路径的长度d2[u] = t;}// 判断u节点是否为无法再继续往下走的节点if (d1[u] == -0x3f3f3f3f){d1[u] = d2[u] = 0;is_leaf[u] = true;}return d1[u];
}void dfs_u(int u, int father)// father为u节点的父节点
{// 遍历u节点的所有出边for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];// 因为此图为无向图，加上此判断，是为了防止在dfs操作的过程中发生死循环if (j == father)continue;// 通过u节点的信息，确定j节点的信息if (p1[u] == j)u1[j] = max(u1[u], d2[u]) + w[i];// w[i]为u节点和其当前子节点（j节点）的边的权值elseu1[j] = max(u1[u], d1[u]) + w[i];// w[i]为u节点和其当前子节点（j节点）的边的权值// 递归进行dfs操作dfs_u(j, u);}
}int main()
{scanf("%d", &n);// 初始化每个节点对应的单链表的表头所指向的idx为-1，表示每个节点与其它节点都不直接相连memset(h, -1, sizeof h);for (int i = 1; i <= n; i++){int a, b, c;scanf("%d %d %d", &a, &b, &c);// 无向图add(a, b, c);add(b, a, c);}/*先随便找一个节点作为整棵树的根节点（这个根节点也是dfs操作的起点），然后按照整棵树的高度依次往下，每个节点（包括根节点）都可以视为是一直往下走或者先往上走的这两种类型的路径的起始节点，据此，即可把树中的所有路径按照节点进行分类，通过dfs操作，枚举每一个节点，相当于枚举树中的所有路径，最终可以在树中找到一个节点，使得该节点到树中其它节点的最大值是其余节点到树中其它节点的最大值中的最小值*//*先确定每个节点所对应的一直往下走所能经过的第一长和第二长的路径的长度（通过子节点的信息，确定父节点的信息）  */dfs_d(1, -1);// 把第一个节点作为整棵树的根节点，根节点的父节点视为无，可设置成一个无效值-1，然后开始进行dfs操作/*然后再确定每个节点所对应的先往上走所能经过的第一长的路径的长度（通过父节点的信息，确定子节点的信息）*/dfs_u(1, -1);// 把第一个节点作为整棵树的根节点，根节点的父节点视为无，可设置成一个无效值-1，然后开始进行dfs操作int res = 0x3f3f3f3f;for (int i = 1; i <= n; i++)if (is_leaf[i])res = min(res, u1[i]);else res = min(res, max(d1[i], u1[i]));// 输出结果printf("%d\n", res);return 0;
}

数字转换

#include <iostream>
#include <cstring>using namespace std;const int N = 5e4 + 10;
const int M = N;int n;
int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条
int sum[N];// 存储每个数的约数之和
bool st[N];// 存储当前节点是否为根节点
int ans;void add(int a, int b)// 插入一条a节点指向b节点的边
{e[idx] = b;ne[idx]= h[a];h[a] = idx++;
}int dfs(int u)
{int d1 = 0;// 存储从u节点出发，一直往下走所能经过的第一长的路径的长度int d2 = 0;// 存储从u节点出发，一直往下走所能经过的第二长的路径的长度// 遍历u节点的所有出边for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];// 递归进行dfs操作，u节点和其当前子节点的边的权值为1int t = dfs(j) + 1;if (t > d1)// 更新从u节点出发，一直往下走所能经过的第一长和第二长的路径的长度{d2 = d1;d1 = t;}else if (t > d2)// 更新从u节点出发，一直往下走所能经过的第二长的路径的长度d2 = t;}ans = max(ans, d1 + d2);return d1;
}int main()
{scanf("%d", &n);// 计算每个数的约数之和，这种做法可以降低时间复杂度for (int i = 1; i <= n; i++)for (int j = 2; i * j <= n; j++)// 因为题目规定每个数的约数不包括它本身，所以j要从2开始sum[i * j] += i;// 初始化每个节点对应的单链表的表头所指向的idx为-1，表示每个节点与其它节点都不直接相连memset(h, -1, sizeof h);for (int i = 2; i <= n; i++)// 因为题目规定所有数字变换在不超过n的正整数范围内进行，所以j要从2开始if (sum[i] < i){// 因为每个数的约数之和只有一个，所以把每个数当作子节点，把每个数的约数之和当作父节点add(sum[i], i);st[i] = true;}// 因为可能存在不止一棵树for (int i = 1; i <= n; i++)// 从每棵树的根节点开始进行dfs操作if (!st[i])dfs(i);// 输出结果printf("%d\n", ans);return 0;
}

二叉苹果树

状态表示
- f[u,j]（f[u,j]表示，在，由，从以u结点为根结点的子树中选择保留并且选择保留的树枝数量不超过j的每种选法的苹果总数量，组成的集合，中，的最大值）
- 在状态表示中仍然可以使用**“不超过”这个限定词来进行状态表示（根据题目的含义可知应该是需要使用“等于”**这个限定词来进行状态表示），并不影响求出正确的结果，因为不存在负权值的边
状态计算
- 要结合树形DP和分组背包问题进行分析

二叉苹果树

#include <iostream>
#include <cstring>using namespace std;const int N = 100 + 10;
const int M = N * 2;int n;
int m;
int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int w[M];// 存储第idx条边的权值
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条
int f[N][M];// 状态表示void add(int a, int b, int c)// 插入一条a节点指向b节点的边，c为边的权值
{w[idx] = c;e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}void dfs(int u, int father)
{/*可以把若干个子节点看成若干组物品，每组物品中根据给当前子节点分配的不同的树枝数量对应有不同的物品，即可视为每组物品中有若干件物品，每件物品可能有不同的价值（因为给当前子节点分配的不同的树枝数量，可能会对应得到不同的苹果总数量），每一组物品中最多只能选一件物品（因为每个子节点只能选一次）此时的思路可以用分组背包问题去考虑，结合分组背包问题的状态表示去理解，实际操作和用一维数组去优化分组背包问题的解题过程相似，此时，f[u][j]的第二维度，等同于，用一维数组去优化分组背包问题的解题过程中的一维数组*//*此时的思路可以用分组背包问题去考虑，结合分组背包问题的状态表示去理解，实际操作和用一维数组去优化分组背包问题的解题过程相似，此时，f[u][j]的第二维度，等同于，用一维数组去优化分组背包问题的解题过程中的一维数组*/for (int i = h[u]; i != -1; i = ne[i])// 依次遍历每组物品（循环物品组）{// 因为此图为无向图，加上此判断，是为了防止在dfs操作的过程中发生死循环if (e[i] == father)continue;// 要结合树形DP进行分析，所以要先进行递归操作dfs(e[i], u);for (int j = m; j >= 0; j--)// 树枝数量从大到小循环（循环树枝数量）/*每组物品中根据给当前子节点分配的不同的树枝数量对应有不同的物品，即可视为每组物品中有若干件物品，每件物品可能有不同的价值（因为给当前子节点分配的不同的树枝数量，可能会对应得到不同的苹果总数量），每一组物品中最多只能选一件物品（因为每个子节点只能选一次）*/// 需要思考分析一下，当j等于0时和当j等于1时，第三层循环会如何进行for (int k = 0; k < j; k++)// 遍历给当前子节点分配的树枝数量（循环决策）f[u][j] = max(f[u][j], f[u][j - 1 - k] + w[i] + f[e[i]][k]);// 注意，通过dfs操作回溯后，这里的f[e[i]][k]是本题目状态表示的含义}
}// 这道题目的思路可以参考有依赖的背包问题的思路，进行分析
int main()
{scanf("%d %d", &n, &m);// 初始化每个节点对应的单链表的表头所指向的idx为-1，表示每个节点与其它节点都不直接相连memset(h, -1, sizeof h);for (int i = 1; i <= n - 1; i++){int a, b, c;scanf("%d %d %d", &a, &b, &c);// 无向图add(a, b, c);add(b, a, c);}// 题目规定根节点的编号为1，根节点的父节点视为无，可设置成一个无效值-1，然后开始进行dfs操作dfs(1, -1);// 输出结果printf("%d\n", f[1][m]);return 0;
}

战略游戏

状态表示
- f[u,0]（f[u,0]表示，在，由，从以u结点为根结点的子树中选择并且不选择u结点的每种选择的士兵总数量，组成的集合，中，的最小值）
- f[u,1]（f[u,1]表示，在，由，从以u结点为根结点的子树中选择并且选择u结点的每种选择的士兵总数量，组成的集合，中，的最小值）
状态计算
- f[u,0]=f[k1,1]+f[k2,1]+…+f[kn,1]（其中k1,k2,…,kn为u结点的子结点）
- f[u,1]=min(f[k1,1],f[k1,0])+min(f[k2,1],f[k2,0])+…+min(f[kn,1],f[kn,0])（其中k1,k2,…,kn为u结点的子结点）

战略游戏

#include <iostream>
#include <cstring>using namespace std;const int N = 1500 + 10;
const int M = N;int n;
int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条边
int f[N][2];// 状态表示
bool st[N];void add(int a, int b)// 插入一条a结点指向b结点的边
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}void dfs(int u)
{// 根据状态表示的含义可得f[u][1] = 1;f[u][0] = 0;// 遍历u结点的所有出边for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];dfs(j);// 递归处理// 状态计算f[u][1] += min(f[j][1], f[j][0]);f[u][0] += f[j][1];}
}int main()
{while (scanf("%d", &n) != -1)// 当scanf没有读到值时，会返回-1{// 初始化每个结点对应的单链表的表头所指向的idx为-1，表示每个结点与其它结点都不直接相连memset(h, -1, sizeof h);idx = 0;memset(st, 0, sizeof st);while (n--){int father, cnt;scanf("%d:(%d)", &father, &cnt);while (cnt--){int son;scanf("%d", &son);add(father, son);st[son] = true;}}int root = 0;// 找到根结点while (st[root])root++;// 从根结点开始进行，状态计算dfs(root);// 输出结果printf("%d\n", min(f[root][1], f[root][0]));}return 0;
}

皇宫看守

状态表示
- f[u,0]（f[u,0]表示，在，由，从以u结点为根结点的子树中选择并且u结点被其父结点看到的每种选择的总花费，组成的集合，中，的最小值）
  - f[u,1]（f[u,1]表示，在，由，从以u结点为根结点的子树中选择并且u结点被其子结点看到的每种选择的总花费，组成的集合，中，的最小值）
  - f[u,2]（f[u,2]表示，在，由，从以u结点为根结点的子树中选择并且u结点被其本身看到的每种选择的总花费，组成的集合，中，的最小值）
状态计算
- f[u,0]=min(f[k1,1],f[k1,2])+min(f[k2,1],f[k2,2])+…+min(f[kn,1],f[kn,2])（其中k1,k2,…,kn为u结点的子结点）
- f[u,1]=min(f[ki,2]+f[u,0]-min(f[ki,1],f[ki,2]))（计算f[u,1]时，需要枚举u结点是被其哪个子结点看到的，ki∈{k1,k2,…,kn}，其中k1,k2,…,kn为u结点的子结点）
- f[u,2]=min(f[k1,0],f[k1,1],f[k1,2])+min(f[k2,0],f[k2,1],f[k2,2])+…+min(f[kn,0],f[kn,1],f[kn,2])（其中k1,k2,…,kn为u结点的子结点）

皇宫看守

#include <iostream>
#include <cstring>using namespace std;const int N = 1500 + 10;
const int M = N;int n;
int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int w[N];// 存储每个节点的费用
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条
int f[N][3];// 状态表示
bool st[N];void add(int a, int b)// 插入一条a结点指向b结点的边
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}void dfs(int u)
{// 根据状态表示的含义可得f[u][2] = w[u];f[u][0] = 0;// 遍历u结点的所有出边for (int i = h[u]; ~i; i = ne[i])// ~i和i!=-1的逻辑判断是一样的{int j = e[i];dfs(j);// 递归处理// 状态计算f[u][0] += min(f[j][1], f[j][2]);// f[root][0]在最终输出结果时，并没有用上，所以没有必要对根结点进行特殊处理f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);}// 当最终递归到叶子结点时，叶子结点并没有子结点，因此可以把f[叶子结点][1]的值赋值为无穷大f[u][1] = 0x3f3f3f3f;// 遍历u结点的所有出边for (int i = h[u]; ~i; i = ne[i]){int j = e[i];// 状态计算f[u][1] = min(f[u][1], f[j][2] + f[u][0] - min(f[j][1], f[j][2]));}
}int main()
{// 初始化每个结点对应的单链表的表头所指向的idx为-1，表示每个结点与其它结点都不直接相连memset(h, -1, sizeof h);scanf("%d", &n);while (n--){int father, temp, cnt;scanf("%d %d %d", &father, &temp, &cnt);w[father] = temp;while (cnt--){int son;scanf("%d", &son);add(father, son);st[son] = true;}}int root = 1;// 找到根结点while (st[root])root++;// 从根结点开始进行，状态计算dfs(root);// 输出结果printf("%d\n", min(f[root][1], f[root][2]));return 0;
}

数位DP

度的数量

#include <iostream>
#include <vector>using namespace std;const int N = 35;int l, r, k, p;
int c[N][N];/*在组合数问题中，我们把从n个不同元素中选出m个元素的组合数，用C(n,m)表示组合数公式中，有一个常用的递推公式：C(n,m)=C(n-1,m)+C(n-1,m-1)举个例子理解这个递推公式：1、现在有n个苹果，在这n个苹果中只存在1个红色苹果，求在n个苹果中选出m个苹果的组合数2、在n个苹果中选出m个苹果可以分为两种情况，第一种情况为选出的m个苹果中不包含红色苹果，第二种情况为选出的m个苹果中包含红色苹果3、在n个苹果中选出m个苹果的组合数（C(n,m)）=先去掉不选的1个红色苹果，在剩下的n-1个苹果中选出m个苹果（C(n-1,m)）+先去掉已选出的1个红色苹果，在剩下的n-1个苹果中选出m-1个苹果（C(n-1,m-1)）
*/
void init()
{for (int i = 0; i < N; i++)for (int j = 0; j <= i; j++)if (!j)c[i][j] = 1;// 当j为0时，则表示从i个不同元素中选出0个元素的组合数，此时组合数为1else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}int dp(int n)
{vector<int> num;// 把n看成p进制数，然后把n中从低位到高位的每一位数字依次放入到num数组中while (n){num.push_back(n % p);n /= p;}int res = 0;int before = 0;// 记录在前面的位置中，已经填了1的位置的个数for (int i = num.size() - 1; i >= 0; i--){int x = num[i];// 只有当当前位上的数大于0时，才存在在当前位上选择填0的情况if (x > 0){// 当在当前位上选择填0时，对应满足条件的数的个数为从剩下i个不同位置中选出k-before个位置填1的组合数res += c[i][k - before];/*当当前位上的数等于1时，如果在当前位上不选择填0的话，那么在当前位上只能选择填1，且后面的位置暂时无法确定选择填什么数，因为要确保是在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数*/if (x == 1){before++;if (before > k)break;}/*当当前位上的数大于1时，如果在当前位上不选择填0的话，那么当在当前位上选择填1时，对应满足条件的数的个数为从剩下i个不同位置中选出k-before-1个位置填1的组合数*/if (x > 1){if (k - before - 1 >= 0)res += c[i][k - before - 1];break;}}// 不要遗漏特殊情况if (!i && k == before)res++;}return res;
}int main()
{// 根据递推公式，先求出所有情况所对应的组合数init();scanf("%d %d %d %d", &l, &r, &k, &p);/*dp(r)表示在1~r中，满足条件的数的个数，dp(l)表示在1~l中，满足条件的数的个数，dp(r)-dp(l-1)表示在l~r中，满足条件的数的个数*/printf("%d\n", dp(r) - dp(l - 1));return 0;
}

数字游戏

状态表示：f[i,j]（f[i,j]表示，一共有i位且最高位为j且从左到右呈现非下降关系，的组合数）
状态计算：f[i,j]=sum(f[i-1][k]+f[i-1][k+1]+f[i-1][k+2]+…+f[i-1][9])（其中，k等于j）

数字游戏

#include <iostream>
#include <vector>using namespace std;const int N = 15;int l, r;
int f[N][10];// 状态表示void init()
{// 根据状态表示可得for (int j = 1; j <= 9; j++)// 因为0不算，所以j从1开始f[1][j] = 1;// 状态计算for (int i = 2; i < N; i++)for (int j = 0; j <= 9; j++)for (int k = j; k <= 9; k++)f[i][j] += f[i - 1][k];
}int dp(int n)
{vector<int> num;// 先把n中从低位到高位的每一位数字依次放入到num数组中while (n){num.push_back(n % 10);n /= 10;}int res = 0;int before = 0;// 记录上一个位置的数字for (int i = num.size() - 1; i >= 0; i--){int x = num[i];if (before > x)// 当无法继续在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数时，直接退出循环即可break;/*当当前位上的数取值为[before,x-1]时，则对应满足条件的数的个数可以直接通过状态表示的值得到*/for (int j = before; j <= x - 1; j++)res += f[i + 1][j];/*当当前位上的数取值为x时，则后面的位置暂时无法确定取值为什么数，因为要确保是在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数*/before = x;// 不要遗漏特殊情况if (!i)res++;}return res;
}int main()
{// 根据递推公式，先求出所有情况所对应的组合数init();while (~scanf("%d %d", &l, &r))/*dp(r)表示在1~r中，满足条件的数的个数，dp(l)表示在1~l中，满足条件的数的个数，dp(r)-dp(l-1)表示在l~r中，满足条件的数的个数*/printf("%d\n", dp(r) - dp(l - 1));return 0;
}

Windy数

状态表示：f[i,j]（f[i,j]表示，一共有i位且最高位为j且从左到右相邻两个数字之差至少为2，的组合数）
状态计算：f[i,j]=sum(f[i-1][k]+f[i-1][k+1]+…+f[i-1][9])（其中，k∈[0,9]，并且j和k之差至少为2）

Windy数

#include <iostream>
#include <vector>
#include <cmath>using namespace std;const int N = 15;int l, r;
int f[N][10];// 状态表示void init()
{// 根据状态表示可得for (int j = 0; j <= 9; j++)// 这里要从0开始，不然会遗漏某些情况f[1][j] = 1;// 状态计算for (int i = 2; i < N; i++)for (int j = 0; j <= 9; j++)for (int k = 0; k <= 9; k++)if (abs(j - k) >= 2)f[i][j] += f[i - 1][k];
}int dp(int n)
{vector<int> num;// 先把n中从低位到高位的每一位数字依次放入到num数组中while (n){num.push_back(n % 10);n /= 10;}int res = 0;int before = -1;// 记录上一个位置的数字for (int i = num.size() - 1; i >= 0; i--){int x = num[i];/*当当前位为最高位时，则最高位从1开始，计算对应满足条件的数的个数*/for (int j = (i == (num.size() - 1)); j < x; j++)if (abs(j - before) >= 2)res += f[i + 1][j];if (abs(x - before) < 2)// 当无法继续在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数时，直接退出循环即可break;/*当当前位上的数取值为x时，则后面的位置暂时无法确定取值为什么数，因为要确保是在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数*/before = x;// 不要遗漏特殊情况if (!i)res++;}// 处理前导0的情况，计算对应满足条件的数的个数for (int i = num.size () - 1; i >= 1; i--)for (int j = 1; j <= 9; j++)res += f[i][j];return res;
}int main()
{// 根据递推公式，先求出所有情况所对应的组合数init();scanf("%d %d", &l, &r);/*dp(r)表示在1~r中，满足条件的数的个数，dp(l)表示在1~l中，满足条件的数的个数，dp(r)-dp(l-1)表示在l~r中，满足条件的数的个数*/printf("%d\n", dp(r) - dp(l - 1));return 0;
}

数字游戏 II

状态表示：f[i,j,k]（f[i,j,k]表示，一共有i位且最高位为j且所有位置上的数字之和模p的结果为0，的组合数。其中，p∈[1,100)）
状态计算：f[i,j,k]=sum(f[i-1][x][(k-j)%p]+f[i-1][x+1][(k-j)%p]+…+f[i-1][9][(k-j)%p])（其中，x∈[0,9]，p∈[1,100)）

数字游戏 II

#include <iostream>
#include <cstring>
#include <vector>using namespace std;const int N = 15;
const int M = 110;int l, r, p;
int f[N][10][M];// 状态表示int mod(int a, int p)
{/*在C++中，计算x % N，如果x为负数则余数为负数，x为正数则余数为正数(x % N + N) % N的目的就是为了让x % N的结果一定变为正数*/return (a % p + p) % p;
}void init()
{// 根据状态表示可得for (int j = 0; j <= 9; j++)// 这里要从0开始，不然会遗漏某些情况f[1][j][mod(j, p)] = 1;// 状态计算for (int i = 2; i < N; i++)for (int j = 0; j <= 9; j++)for (int k = 0; k < p; k++)for (int x = 0; x <= 9; x++)f[i][j][k] += f[i - 1][x][mod(k - j, p)];
}int dp(int n)
{if (!n)return 1;vector<int> num;// 先把n中从低位到高位的每一位数字依次放入到num数组中while (n){num.push_back(n % 10);n /= 10;}int res = 0;int before = 0;// 记录在前面的所有位置上的数字之和for (int i = num.size() - 1; i >= 0; i--){int x = num[i];/*当当前位上的数取值为[0,x-1]时，则对应满足条件的数的个数可以直接通过状态表示的值得到*/for (int j = 0; j < x; j++)res += f[i + 1][j][mod(0 - before, p)];/*当当前位上的数取值为x时，则后面的位置暂时无法确定取值为什么数，因为要确保是在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数*/before += x;// 不要遗漏特殊情况if (!i && mod(before, p) == 0)res++;}return res;
}int main()
{while (~scanf("%d %d %d", &l, &r, &p)){memset(f, 0, sizeof f);// 根据递推公式，先求出所有情况所对应的组合数init();/*dp(r)表示在1~r中，满足条件的数的个数，dp(l)表示在1~l中，满足条件的数的个数，dp(r)-dp(l-1)表示在l~r中，满足条件的数的个数*/printf("%d\n", dp(r) - dp(l - 1));}return 0;
}

不要62

状态表示：f[i,j]（f[i,j]表示，一共有i位且最高位为j且从左到右不含4或者62，的组合数）
状态计算：f[i,j]=sum(f[i-1][k]+f[i-1][k+1]+…+f[i-1][9])（其中，k∈[0,9]，j不等于4，k不等于4，并且当j等于6时k不等于2）

不要62

#include <iostream>
#include <cstring>
#include <vector>using namespace std;const int N = 15;int f[N][10];// 状态表示
int l, r;void init()
{// 根据状态表示可得for (int j = 0; j <= 9; j++)// 这里要从0开始，不然会遗漏某些情况if (j != 4)f[1][j] = 1;// 状态计算for (int i = 2; i < N; i++)for (int j = 0; j <= 9; j++)if (j != 4)for (int k = 0; k <= 9; k++){if (k == 4 || (j == 6 && k == 2))continue;f[i][j] += f[i - 1][k];}
}int dp(int n)
{if (!n)return 1;vector<int> num;// 先把n中从低位到高位的每一位数字依次放入到num数组中while (n){num.push_back(n % 10);n /= 10;}int res = 0;int before = 0;// 记录上一个位置的数字for (int i = num.size() - 1; i >= 0; i--){int x = num[i];/*当当前位上的数取值为[0,x-1]时，则对应满足条件的数的个数可以直接通过状态表示的值得到*/for (int j = 0; j <= x - 1; j++){if (j == 4 || (before == 6 && j == 2))continue;res += f[i + 1][j];}if (x == 4 || (before == 6 && x == 2))// 当无法继续在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数时，直接退出循环即可break;/*当当前位上的数取值为x时，则后面的位置暂时无法确定取值为什么数，因为要确保是在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数*/before = x;// 不要遗漏特殊情况if (!i)res++;}return res;
}int main()
{while (scanf("%d %d", &l, &r), l || r)// 也可以这么写，这个叫逗号表达式。逗号表达式的真假只等于最后一个数的真假{memset(f, 0, sizeof f);// 根据递推公式，先求出所有情况所对应的组合数init();/*dp(r)表示在1~r中，满足条件的数的个数，dp(l)表示在1~l中，满足条件的数的个数，dp(r)-dp(l-1)表示在l~r中，满足条件的数的个数*/printf("%d\n", dp(r) - dp(l - 1));}return 0;
}

恨7不成妻

状态表示：f[i,j,a,b]（f[i,j,a,b]表示，在，由，一共有i位且最高位为j且所有位置上的数字不包含7且这个整数模7的结果为a且所有位置上的数字之和模7的结果为b，组成的集合，中，的每个数的0次方的和、与每个数的1次方的和、与每个数的2次方的和。其中，j不等于7）
状态计算：f[i,j,a,b]=f[i-1,k,(a-j*10^(i-1))%7,(b-j)%7]（其中，j不等于7，k不等于7）

恨7不成妻

#include <iostream>
#include <cstring>
#include <vector>using namespace std;typedef long long LL;const int N = 19;
const int P = 1e9 + 7;struct F
{int s0 = 0;// 所有满足条件的数的0次方的和int s1 = 0;// 所有满足条件的数的1次方的和int s2 = 0;// 所有满足条件的数的2次方的和
}f[N][10][7][7];// 状态表示
int power7[N];// 存储10的i次方模7的结果
int powerP[N];// 存储10的i次方模P的结果int mod(LL a, int p)
{/*在C++中，计算x % N，如果x为负数则余数为负数，x为正数则余数为正数(x % N + N) % N的目的就是为了让x % N的结果一定变为正数*/return (a % p + p) % p;
}void init()
{// 根据状态表示可得for (int j = 0; j <= 9; j++)// 这里要从0开始，不然会遗漏某些情况if (j != 7){F &v = f[1][j][j % 7][j % 7];v.s0 = 1;v.s1 = j;v.s2 = j * j;}LL power = 10;// 状态计算for (int i = 2; i < N; i++, power *= 10)for (int j = 0; j <= 9; j++)if (j != 7)for (int a = 0; a < 7; a++)for (int b = 0; b < 7; b++)for (int k = 0; k <= 9; k++)if (k != 7){F &v1 = f[i][j][a][b];F &v2 = f[i - 1][k][mod(a - j * power, 7)][mod(b - j, 7)];// 在C++中，一个int类型的整数和一个long long类型的整数相乘时，它们相乘的结果的类型为long long类型// 一定要注意取模的技巧，即要把long long类型的结果的范围及时限制在0~(P-1)的范围内，然后再继续进行计算v1.s0 = mod(v1.s0 + v2.s0, P);v1.s1 = mod(v1.s1 + j * power % P * v2.s0 + v2.s1, P);v1.s2 = mod(v1.s2 + j * j * (power % P) % P * (power % P) % P * v2.s0 + v2.s2 + 2 * j * (power % P) % P * v2.s1,P);}
}/*返回，在，由，一共有i位且最高位为j且所有位置上的数字不包含7且这个整数模7的结果不为a且所有位置上的数字之和模7的结果不为b，组成的集合，中，的每个数的0次方的和、与每个数的1次方的和、与每个数的2次方的和
*/
F get(int i, int j, int a, int b)
{int s0 = 0;// 所有满足条件的数的0次方的和int s1 = 0;// 所有满足条件的数的1次方的和int s2 = 0;// 所有满足条件的数的2次方的和for (int x = 0; x < 7; x++)for (int y = 0; y < 7; y++)if (x != a && y != b){F &v = f[i][j][x][y];s0 = (s0 + v.s0) % P;s1 = (s1 + v.s1) % P;s2 = (s2 + v.s2) % P;}return {s0, s1, s2};
}int dp(LL n)
{if (!n)return 0;LL backup_n = n;vector<int> num;// 先把n中从低位到高位的每一位数字依次放入到num数组中while (n){num.push_back(n % 10);n /= 10;}int res = 0;LL before_a = 0;// 记录在前面的所有位置上的数字所组成的整数int before_b = 0;// 记录在前面的所有位置上的数字之和for (int i = num.size() - 1; i >= 0; i--){int x = num[i];/*当当前位上的数取值为[0,x-1]时，则对应满足条件的数的平方和可以结合状态表示分析得到*/for (int j = 0; j < x; j++)if (j != 7){F v = get(i + 1, j, mod(0 - before_a * power7[i + 1], 7), mod(0 - before_b, 7));// 在C++中，一个int类型的整数和一个long long类型的整数相乘时，它们相乘的结果的类型为long long类型// 一定要注意取模的技巧，即要把long long类型的结果的范围及时限制在0~(P-1)的范围内，然后再继续进行计算res = mod(res + (before_a % P) * (before_a % P) % P * powerP[i + 1] % P * powerP[i + 1] % P * v.s0 + v.s2 + 2 * (before_a % P) * powerP[i + 1] % P * v.s1, P);}// 当无法继续在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数时，直接退出循环即可if (x == 7)break;/*当当前位上的数取值为x时，则后面的位置暂时无法确定取值为什么数，因为要确保是在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数*/before_a = before_a * 10 + x;before_b += x;// 不要遗漏特殊情况if (!i && before_a % 7 && before_b % 7)res = (res + (backup_n % P) * (backup_n % P)) % P;}return res;
}int main()
{int n;scanf("%d", &n);while (n--){memset(f, 0, sizeof f);// 初始化处理init();power7[0] = 1;// 计算10的i次方模7的结果for (int i = 1; i < N; i++)power7[i] = power7[i - 1] * 10 % 7;powerP[0] = 1;// 计算10的i次方模P的结果for (int i = 1; i < N; i++)// 在C++中，如果两个int类型的整数相乘的结果会溢出，则要先把int类型的整数改成long long类型，然后再进行相乘powerP[i] = (LL)powerP[i - 1] * 10 % P;LL l, r;scanf("%lld %lld", &l, &r);/*dp(r)表示在1~r中，满足条件的数的个数，dp(l)表示在1~l中，满足条件的数的个数，dp(r)-dp(l-1)表示在l~r中，满足条件的数的个数*/// 因为dp函数中返回的结果是经过取模后的结果，所以可能存在dp(r)<dp(l-1)的情况，所以需要使用mod函数进行取模printf("%d\n", mod(dp(r) - dp(l - 1), P));}return 0;
}

单调队列优化DP

最大子序和

#include <iostream>
#include <limits.h>using namespace std;const int N = 3e5 + 10;int s[N];// 前缀和数组
int q[N];// 滑动窗口的数组（用数组模拟队列），这里的q数组记录的值是s数组的下标
int n;
int k;// 滑动窗口的大小int main()
{scanf("%d %d", &n, &k);for (int i = 1; i <= n; i++){scanf("%d", &s[i]);s[i] += s[i - 1];}int res = INT_MIN;// INT_MIN表示int类型的最小值，需要引入头文件limits.h才可以使用// 一开始设定，队头为0，队尾为0，则有hh<=tt，表示队列一开始就不为空int hh = 0, tt = 0;for (int i = 1; i <= n; i++){if (q[hh] < i - k)// 因为s数组是前缀和数组，所以这里是q[hh]<i-k，而不是q[hh]<i-k+1hh++;// 只要保证在s[r]-s[l-1]中的s[l-1]为最小值，即可保证s[r]-s[l-1]的结果取到最大值res = max(res, s[i] - s[q[hh]]);// 当前队列队头对应的s数组的下标的值即为滑动窗口中的最小值// 当队列不为空，且队尾对应的s数组的下标的值大于等于当前遍历到的s[i]，则弹出队尾元素// 保证队列的单调性while (hh <= tt && s[q[tt]] >= s[i])tt--;// 这里的q数组记录的值是s数组的下标q[++tt] = i;}printf("%d\n", res);return 0;
}

旅行问题

#include <iostream>using namespace std;const int N = 2 * 1e6 + 10;// 因为要破环成链，所以是2 * 1e6 + 10int n;
int o[N], d[N];
long long s[N];// 前缀和数组
int q[N];// 滑动窗口的数组（用数组模拟队列），这里的q数组记录的值是s数组的下标
bool st[N];int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d %d", &o[i], &d[i]);// 顺时针for (int i = 1; i <= n; i++)s[i] = s[i + n] = o[i] - d[i];for (int i = 1; i <= 2 * n; i++)s[i] += s[i - 1];int hh = 0, tt = -1;// 一开始设定，队头为0，队尾为-1q[0] = 2 * n - 1;for (int i = 2 * n - 1; i >= 0; i--){if (q[hh] > i + n)// 判断队头对应的s数组的下标是否已经超出窗口的范围hh++;if (i <= n - 1)// 只要保证在s[q[hh]]-s[i]中的s[q[hh]]为最小值，即可保证s[q[hh]]-s[i]的结果取到最小值// 当s[q[hh]]-s[i]的结果取到最小值时，仍然大于等于0，则表示从i+1出发，能朝顺时针方向走一圈回到原点if (s[q[hh]] - s[i] >= 0)st[i + 1] = true;// 当队列不为空，且队尾对应的s数组的下标的值大于等于当前遍历到的s[i]，则弹出队尾元素// 保证队列的单调性while (hh <= tt && s[q[tt]] >= s[i])tt--;q[++tt] = i;// 这里的q数组记录的值是s数组的下标}// 逆时针d[0] = d[n];for (int i = 1; i <= n; i++)s[i] = s[i + n] = o[i] - d[i - 1];for (int i = 1; i <= 2 * n; i++)s[i] += s[i - 1];hh = 0, tt = -1;// 一开始设定，队头为0，队尾为-1q[0] = 1;for (int i = 1; i <= 2 * n; i++){if (q[hh] < i - n)// 判断队头对应的s数组的下标是否已经超出窗口的范围hh++;if (i >= n + 1)// 只要保证在s[i]-s[q[hh]]中的s[q[hh]]为最大值，即可保证s[i]-s[q[hh]]的结果取到最小值// 当s[i]-s[q[hh]]的结果取到最小值时，仍然大于等于0，则表示从i-n出发，能朝逆时针方向走一圈回到原点if (s[i] - s[q[hh]] >= 0)st[i - n] = true;// 当队列不为空，且队尾对应的s数组的下标的值小于等于当前遍历到的s[i]，则弹出队尾元素// 保证队列的单调性while (hh <= tt && s[q[tt]] <= s[i])tt--;q[++tt] = i;// 这里的q数组记录的值是s数组的下标}// 输出结果for (int i = 1; i <= n; i++)if (st[i])printf("TAK\n");elseprintf("NIE\n");return 0;
}

烽火传递

状态表示：f[i]（f[i]表示，在，由，从1到i中不包含连续k个烽火台里面没有点燃的烽火台的情况且点燃第i个烽火台的每种选法的总代价，组成的集合，中，的最小值）
状态计算：f[i]=min(f[j]+w[i])（其中，j∈[i-k,i-1]）

烽火传递

#include <iostream>using namespace std;const int N = 2e6 + 10;int n;
int k;// 滑动窗口的大小
int w[N];
int f[N];
int q[N];// 滑动窗口的数组（用数组模拟队列），这里的q数组记录的值是f数组的下标int main()
{scanf("%d %d", &n, &k);for (int i = 1; i <= n; i++)scanf("%d", &w[i]);// 一开始设定，队头为0，队尾为0，则有hh<=tt，表示队列一开始就不为空int hh = 0, tt = 0;for (int i = 1; i <= n; i++){if (q[hh] < i - k)// 判断队头对应的f数组的下标是否已经超出窗口的范围hh++;// 状态计算f[i] = f[q[hh]] + w[i];// 当前队列队头对应的f数组的下标的值即为滑动窗口中的最小值// 当队列不为空，且队尾对应的f数组的下标的值大于等于当前遍历到的f[i]，则弹出队尾元素// 保证队列的单调性while (hh <= tt && f[q[tt]] >= f[i])tt--;// 这里的q数组记录的值是f数组的下标q[++tt] = i;}int res = 1e9;for (int i = n - k + 1; i <= n; i++)res = min(res, f[i]);// 输出结果    printf("%d\n", res);return 0;
}

绿色通道

#include <iostream>using namespace std;const int N = 5e4 + 10;int n;
int t;
int w[N];
int f[N];
int q[N];// 滑动窗口的数组（用数组模拟队列），这里的q数组记录的值是f数组的下标// 判断最长的空题段在不超过limit且抄上第i个题目的情况下，最少需要花费的代价是否小于等于给定的t
bool check(int limit)// limit为滑动窗口的大小
{// 一开始设定，队头为0，队尾为0，则有hh<=tt，表示队列一开始就不为空int hh = 0, tt = 0;for (int i = 1; i <= n; i++){if (q[hh] < i - limit - 1)// 判断队头对应的f数组的下标是否已经超出窗口的范围hh++;// 状态计算    f[i] = f[q[hh]] + w[i];// 当前队列队头对应的f数组的下标的值即为滑动窗口中的最小值// 当队列不为空，且队尾对应的f数组的下标的值大于等于当前遍历到的f[i]，则弹出队尾元素// 保证队列的单调性while (hh <= tt && f[q[tt]] >= f[i])tt--;// 这里的q数组记录的值是f数组的下标q[++tt] = i;}int res = 1e9;for (int i = n - limit; i <= n; i++)res = min(res, f[i]);// 判断最长的空题段在不超过limit的情况下，最少需要花费的代价是否小于等于给定的t    if (res <= t)return true;elsereturn false;
}int main()
{scanf("%d %d", &n, &t);for (int i = 1; i <= n; i++)scanf("%d", &w[i]);int l = 0;// 二分区间的左边界int r = n;// 二分区间的右边界while (l < r){int mid = (l + r) / 2;if (check(mid))r = mid;// 这里是二分右区间的左端点elsel = mid + 1;}printf("%d\n", r);return 0;
}

修剪草坪

状态表示：f[i]（f[i]表示，在，由，从1到i中不包含超过连续k只奶牛的每种选法的总效率，组成的集合，中，的最大值）
状态计算：f[i]=max(f[i-1],f[i-j-1]+s[i]-s[i-j])（其中，j∈[1,k]，s数组表示前缀和）

修剪草坪

#include <iostream>using namespace std;typedef long long LL;const int N = 1e5 + 10;int n;
int k;// 滑动窗口的大小
LL s[N];// 前缀和数组
LL f[N];// 状态表示
int q[N];// 滑动窗口的数组（用数组模拟队列）LL g(int x)
{if (!x)return 0;return f[x - 1] - s[x];
}int main()
{scanf("%d %d", &n, &k);for (int i = 1; i <= n; i++){scanf("%lld", &s[i]);s[i] += s[i - 1];}// 一开始设定，队头为0，队尾为0，则有hh<=tt，表示队列一开始就不为空int hh = 0, tt = 0;for (int i = 1; i <= n; i++){if (q[hh] < i - k)// 判断队头是否已经超出窗口的范围hh++;// 状态计算f[i] = max(f[i - 1], g(q[hh]) + s[i]);// 保证队列的单调性while (hh <= tt && g(q[tt]) <= g(i))tt--;q[++tt] = i;}// 输出结果printf("%lld\n", f[n]);return 0;
}

理想的正方形

#include <iostream>using namespace std;const int N = 1e3 + 10;int n, m;
int k;// 滑动窗口的大小
int w[N][N];
int row_max[N][N];
int row_min[N][N];
int q[N];// 滑动窗口的数组（用数组模拟队列）// 单调队列求滑动窗口中的最大值
void get_max(int a[], int right_end, int b[])
{int hh = 0, tt = -1;// 一开始设定，队头为0，队尾为-1for (int j = 1; j <= right_end; j++){if (q[hh] <= j - k)// 判断队头是否已经超出窗口的范围hh++;// 保证队列的单调性while (hh <= tt && a[q[tt]] <= a[j])tt--;q[++tt] = j;b[j] = a[q[hh]];}
}// 单调队列求滑动窗口中的最小值
void get_min(int a[], int right_end, int b[])
{int hh = 0, tt = -1;// 一开始设定，队头为0，队尾为-1for (int j = 1; j <= right_end; j++){if (q[hh] <= j - k)// 判断队头是否已经超出窗口的范围hh++;// 保证队列的单调性while (hh <= tt && a[q[tt]] >= a[j])tt--;q[++tt] = j;b[j] = a[q[hh]];}
}int main()
{scanf("%d %d %d", &n, &m, &k);for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)scanf("%d", &w[i][j]);// 处理每一行，每一行分别求出滑动窗口中的最大值、最小值for (int i = 1; i <= n; i++){get_max(w[i], m, row_max[i]);get_min(w[i], m, row_min[i]);}int res = 1e9;int a[n], b[n], c[n];for (int j = k; j <= m; j++)// 这里要从k开始{for (int i = 1; i <= n; i++)a[i] = row_max[i][j];get_max(a, n, b);for (int i = 1; i <= n; i++)a[i] = row_min[i][j];get_min(a, n, c);for (int i = k; i <= n; i++)// 这里要从k开始res = min(res, b[i] - c[i]);}// 输出结果printf("%d\n", res);return 0;
}

斜率优化DP

任务安排1

状态表示：f[i]（f[i]表示，在，由，将前i个任务分批加工的每种选法的总费用，组成的集合，中，的最小值）
*状态计算：f[i]=min(f[j]+(sumc[i]-sumc[j])sumt[i]+(sumc[n]-sumc[j])*s)（其中，j∈{0,1,2,…,i-1}，sumc数组、sumt数组表示前缀和，s表示机器的准备时间）

任务安排1

#include <iostream>
#include <cstring>using namespace std;typedef long long LL;const int N = 1e5 + 10;int n;
int s;
int sumt[N], sumc[N];
LL f[N];// 状态表示int main()
{scanf("%d %d", &n, &s);for (int i = 1; i <= n; i++){scanf("%d %d", &sumt[i], &sumc[i]);sumt[i] += sumt[i - 1];sumc[i] += sumc[i - 1];}memset(f, 0x3f3f3f3f, sizeof f);f[0] = 0;// 根据状态表示可得// 状态计算for (int i = 1; i <= n; i++)for (int j = 0; j <= i - 1; j++)f[i] = min(f[i], f[j] + (LL)(sumc[i] - sumc[j]) * sumt[i] + (LL)(sumc[n] - sumc[j]) * s);// 输出结果printf("%lld\n", f[n]);return 0;
}

任务安排2

状态表示：f[i]（f[i]表示，在，由，将前i个任务分批加工的每种选法的总费用，组成的集合，中，的最小值）
*状态计算：f[i]=min(f[j]+(sumc[i]-sumc[j])sumt[i]+(sumc[n]-sumc[j])*s)（其中，j∈{0,1,2,…,i-1}，sumc数组、sumt数组表示前缀和，s表示机器的准备时间）

任务安排2

#include <iostream>using namespace std;typedef long long LL;const int N = 3e5 + 10;int n;
int s;
LL t[N], c[N];
LL f[N];// 状态表示
int q[N];int main()
{scanf("%d %d", &n, &s);for (int i = 1; i <= n; i++){scanf("%lld %lld", &t[i], &c[i]);t[i] += t[i - 1];c[i] += c[i - 1];}int hh = 0, tt = 0;q[hh] = 0;// 状态计算的最开始一定是从(c[0],f[0])转移过来的/*状态计算，f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n]，把f[j]看成y，把(t[i]+s)看成k，把c[j]看成x，则有，f[i] = y - k * x + t[i] * c[i] + s * c[n]，继续变形，则有，y = k * x + f[i] - t[i] * c[i] - s * c[n]，把f[i]-t[i]*c[i]-s*c[n]看成b，则有，y = k * x + b，要想让f[i]取到最小值，即让b取到最小值，即让状态计算中的截距取到最小值，此时就要在当前斜率k的情况下，找到穿过前面的哪个点(c[j],f[j])可以让状态计算中的截距取到最小值，通过画图思考分析可以知道，因为斜率k是一直在变大的，所以寻找穿过前面的哪个点(c[j],f[j])的这个过程，可以使用单调队列来优化*/for (int i = 1; i <= n; i++){/*当hh<tt时，则表示可选择穿过的前面的点的数量大于等于2个，通过画图思考分析可以知道，因为斜率k是一直在变大的，所以寻找穿过前面的哪个点(c[j],f[j])的这个过程，可以使用单调队列来优化，把已经不可能再被选择穿过的前面的点(c[j],f[j])及时地干掉即可*/while (hh < tt && (f[q[hh + 1]] - f[q[hh]]) <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]]))hh++;// 在当前斜率k的情况下，穿过前面的这个点(c[q[hh]],f[q[hh]])可以让状态计算中的截距取到最小值int j = q[hh];// 状态计算f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];// 把已经不可能再被选择穿过的前面的点(c[j],f[j])及时地干掉即可while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]]))tt--;q[++tt] = i;}// 输出结果printf("%lld\n", f[n]);return 0;
}

任务安排3

状态表示：f[i]（f[i]表示，在，由，将前i个任务分批加工的每种选法的总费用，组成的集合，中，的最小值）
*状态计算：f[i]=min(f[j]+(sumc[i]-sumc[j])sumt[i]+(sumc[n]-sumc[j])*s)（其中，j∈{0,1,2,…,i-1}，sumc数组、sumt数组表示前缀和，s表示机器的准备时间）

任务安排3

#include <iostream>using namespace std;typedef long long LL;const int N = 3e5 + 10;int n;
int s;
LL t[N], c[N];
LL f[N];// 状态表示
int q[N];int main()
{scanf("%d %d", &n, &s);for (int i = 1; i <= n; i++){scanf("%lld %lld", &t[i], &c[i]);t[i] += t[i - 1];c[i] += c[i - 1];}int hh = 0, tt = 0;q[hh] = 0;// 状态计算的最开始一定是从(c[0],f[0])转移过来的/*状态计算，f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n]，把f[j]看成y，把(t[i]+s)看成k，把c[j]看成x，则有，f[i] = y - k * x + t[i] * c[i] + s * c[n]，继续变形，则有，y = k * x + f[i] - t[i] * c[i] - s * c[n]，把f[i]-t[i]*c[i]-s*c[n]看成b，则有，y = k * x + b，要想让f[i]取到最小值，即让b取到最小值，即让状态计算中的截距取到最小值，此时就要在当前斜率k的情况下，找到穿过前面的哪个点(c[j],f[j])可以让状态计算中的截距取到最小值，通过画图思考分析可以知道，因为斜率k并不是一直在变大的，所以寻找穿过前面的哪个点(c[j],f[j])的这个过程，可以使用二分查找来优化*/for (int i = 1; i <= n; i++){int l = hh, r = tt;/*当hh<tt时，则表示可选择穿过的前面的点的数量大于等于2个，通过画图思考分析可以知道，因为斜率k并不是一直在变大的，所以寻找穿过前面的哪个点(c[j],f[j])的这个过程，可以使用二分查找来优化*/while (l < r){int mid = (l + r) / 2;if ((f[q[mid + 1]] - f[q[mid]]) > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]]))r = mid;elsel = mid + 1;}// 在当前斜率k的情况下，穿过前面的这个点(c[q[r]],f[q[r]])可以让状态计算中的截距取到最小值int j = q[r];// 状态计算f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];// 把已经不可能再被选择穿过的前面的点(c[j],f[j])及时地干掉即可while (hh < tt && (__int128)(f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (__int128)(f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]]))tt--;q[++tt] = i;}// 输出结果printf("%lld\n", f[n]);return 0;
}

运输小猫

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef long long LL;const int N = 1e5 + 10;
const int M = 1e5 + 10;
const int P = 100 + 10;int n, m, p;
LL d[N];
LL a[M], s[M];
LL f[P][M];// 状态表示
int q[M];LL get_y(int k, int j)
{return f[j - 1][k] + s[k];
}/*解题思路：1、假设某个饲养员的出发时间为S，则该饲养员能把在第i座山上的小猫接走，需要满足的条件为，S>=t-d[i]（其中，t为在第i座山上的小猫的玩耍结束时间，d[i]为在第i座山上的小猫距离1号山的长度）2、假设某个饲养员的出发时间为S，则第i座山上的小猫需要等待的时间为S-(t-d[i])3、一共有m只小猫，把每只小猫对应的t和d[i]所构成的t-d[i]设为a[i]，然后把m个a[i]按照从小到大进行排序，a[1],a[2],a[3],......,a[m]4、根据a[1],a[2],a[3],......,a[m]，可得，假设某个饲养员要接走a[1],a[2],a[3]这三只小猫，则该饲养员最早的出发时间为a[3]，则a[1],a[2],a[3]这三只小猫等待的时间总和为，(a[3]-a[1])+(a[3]-a[2])+(a[3]-a[3])，化简可得，a[3]*(3-0)-(a[1]+a[2]+a[3])5、此时，即可把问题转化为求，让p个饲养员接走m个小猫，m个小猫等待的时间总和，的最小值，根据a[1],a[2],a[3],......,a[m]，可得，状态表示：f[j][i]（f[j][i]表示，在，由，将前i个小猫接走且饲养员的数量不超过j个的每种选法的小猫等待的时间总和，组成的集合，中，的最小值）状态计算：f[j][i]=min(f[j-1][k]+a[i]*(i-k)-(s[i]-s[k]))（其中s数组为a[1],a[2],a[3],......,a[m]的前缀和数组，k∈{0,1,2,...,j-1}）
*/
int main()
{scanf("%d %d %d", &n, &m, &p);for (int i = 2; i <= n; i++){scanf("%lld", &d[i]);d[i] += d[i - 1];}for (int i = 1; i <= m; i++){int h;LL t;scanf("%d %lld", &h, &t);a[i] = t - d[h];}sort(a + 1, a + m + 1);// 从小到大进行排序for (int i = 1; i <= m; i++)s[i] = s[i - 1] + a[i];// 根据状态表示可得for (int i = 1; i <= m; i++)f[0][i] = 0x3f3f3f3f3f3f3f3f;/*状态计算，f[j][i] = f[j - 1][k] + s[k] - a[i] * k + a[i] * i - s[i]，把f[j-1][k]+s[k]看成y，把a[i]看成K（斜率），把k看成x，则有，f[j][i] = y - K * x + a[i] * i - s[i]，继续变形，则有，y = K * x + f[j][i] - a[i] * i + s[i]，把f[j][i]-a[i]*i+s[i]看成b，则有，y = K * x + b，要想让f[j][i]取到最小值，即让b取到最小值，即让状态计算中的截距取到最小值，此时就要在当前斜率K的情况下，找到穿过前面的哪个点(k,f[j-1][k]+s[k])可以让状态计算中的截距取到最小值，通过画图思考分析可以知道，因为斜率K是一直在变大的，所以寻找穿过前面的哪个点(k,f[j-1][k]+s[k])的这个过程，可以使用单调队列来优化*/for (int j = 1; j <= p; j++){int hh = 0, tt = 0;q[hh] = 0;// 状态计算的最开始一定是从(0,f[j-1][0]+s[0])转移过来的for (int i = 1; i <= m; i++){/*当hh<tt时，则表示可选择穿过的前面的点的数量大于等于2个，通过画图思考分析可以知道，因为斜率K是一直在变大的，所以寻找穿过前面的哪个点(k,f[j-1][k]+s[k])的这个过程，可以使用单调队列来优化，把已经不可能再被选择穿过的前面的点(k,f[j-1][k]+s[k])及时地干掉即可*/while (hh < tt && (get_y(q[hh + 1], j) - get_y(q[hh], j)) <= a[i] * (q[hh + 1] - q[hh]))hh++;// 在当前斜率K的情况下，穿过前面的这个点(q[hh],f[j-1][q[hh]]+s[q[hh]])可以让状态计算中的截距取到最小值    int k = q[hh];// 状态计算f[j][i] = f[j - 1][k] + s[k] - a[i] * k + a[i] * i - s[i];// 把已经不可能再被选择穿过的前面的点(k,f[j-1][k]+s[k])及时地干掉即可while (hh < tt && (get_y(q[tt], j) - get_y(q[tt - 1], j)) * (i - q[tt - 1]) >= (get_y(i, j) - get_y(q[tt - 1], j)) * (q[tt] - q[tt - 1]))tt--;q[++tt] = i;}}// 输出结果printf("%lld\n", f[p][m]);return 0;
}

习题

环形石子合并

#include <iostream>
#include <cstring>using namespace std;const int N = 400 + 10;int n;
int f[N][N];// 状态表示，计算最小值
int g[N][N];// 状态表示，计算最大值
int w[N];// 存储每堆石子的重量
int s[N];// 前缀和数组int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++){scanf("%d", &w[i]);w[i + n] = w[i];// 通过这样的操作，即可把环形石子问题，转化为线性石子问题}for (int i = 1; i <= 2 * n; i++)s[i] = s[i -  1]  + w[i];// 前缀和memset(f, 0x3f, sizeof f);memset(g, -0x3f, sizeof g);// 按区间长度从小到大进行遍历for (int len = 1; len <= n; len++)// 区间长度从1开始// 遍历当前区间长度的左边界for (int l = 1; l + len - 1 <= 2 * n; l++){int r = l + len - 1;// 右边界if (len == 1)f[l][r] = g[l][r] = 0;else// 状态计算for (int k = l; k < r; k++){f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);}}int min_res = 0x3f3f3f3f;int max_res = -0x3f3f3f3f;for (int i = 1; i <= n + 1; i++){min_res = min(min_res, f[i][i + n - 1]);max_res = max(max_res, g[i][i + n - 1]);}// 输出结果printf("%d\n%d\n", min_res, max_res);return 0;
}

能量项链

#include <iostream>using namespace std;const int N = 200 + 10;int n;
int f[N][N];// 状态表示
int w[N];int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++){scanf("%d", &w[i]);w[i + n] = w[i];// 通过这样的操作，即可把环形问题，转化为线性问题}w[2 * n + 1] = w[1];// 加上这一行是为了和解题的思路更加吻合// 按区间长度从小到大进行遍历// 区间长度从3开始，是因为至少要有两颗能量珠才能进行合并，才有意义// 注意，这里的区间长度的上限为n+1for (int len = 3; len <= n + 1; len++)// 遍历当前区间长度的左边界for (int l = 1; l + len - 1 <= 2 * n + 1; l++){int r = l + len - 1;// 右边界// 状态计算for (int k = l + 1; k < r; k++)f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);}int res = 0;for (int i = 1; i <= n + 1; i++)res = max(res, f[i][i + n]);// 从i到i+n的长度为n+1// 输出结果    printf("%d\n", res);return 0;
}

加分二叉树

#include <iostream>using namespace std;const int N = 30 + 10;int n;
int w[N];
int f[N][N];// 状态表示
int g[N][N];// 记录当前二叉树的根节点void dfs(int l, int r)// 递归输出最终求得的二叉树的前序遍历（根节点--->左节点--->右节点）
{if (r < l)return;int k = g[l][r];printf("%d ", k);dfs(l, k - 1);dfs(k + 1, r);
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &w[i]);// 按区间长度从小到大进行遍历for (int len = 1; len <= n; len++)// 遍历当前区间长度的左边界for (int l = 1; l + len - 1 <= n; l++){int r = l + len - 1;// 右边界if (len == 1){f[l][r] = w[l];g[l][r] = l;// 记录当前二叉树的根节点}else{// 状态计算for (int k = l; k <= r; k++){// 若k为左端点，则当前以k为根节点的二叉树的左子树的加分为1int left = k == l ? 1 : f[l][k - 1];// 若k为右端点，则当前以k为根节点的二叉树的右子树的加分为1int right = k == r ? 1 : f[k + 1][r];if (f[l][r] < left * right + w[k])// 因为要输出字典序最小的方案，所以这里不能用<=，只能用<{f[l][r] = left * right + w[k];g[l][r] = k;// 记录当前二叉树的根节点}}}}printf("%d\n", f[1][n]);// 输出结果dfs(1, n);// 递归输出最终求得的二叉树的前序遍历（根节点--->左节点--->右节点）return 0;
}

凸多边形的划分

#include <iostream>
#include <cstring>using namespace std;typedef long long LL;const int N = 55;
const int M = 35;// 最终的十进制表示的值，长度不会超过35位int n;
int w[N];// 存储每个结点的权值
LL f[N][N][M];// 数组的前两维用于状态表示，数组的第三维用于存储当前状态表示的（高精度）值void mul(LL a[], int b)// 高精度乘法
{LL res[M];memset(res, 0, sizeof res);// 局部变量要赋值，否则存储的是随机值，会影响计算LL t = 0;for (int i = 0; i < M; i++){t = a[i] * b + t;res[i] = t % 10;t = t / 10;}memcpy(a, res, sizeof res);
}void add(LL a[], LL b[])// 高精度加法
{LL res[M];memset(res, 0, sizeof res);// 局部变量要赋值，否则存储的是随机值，会影响计算LL t = 0;for (int i = 0; i < M; i++){t = a[i] + b[i] + t;res[i] = t % 10;t = t / 10;}memcpy(a, res, sizeof res);
}int cmp(LL a[], LL b[])// 高精度比较大小
{for (int i = M - 1; i >= 0; i--)if (a[i] > b[i])return 1;else if (a[i] < b[i])return -1;return 0;
}void res_printf(LL a[])// 高精度打印输出
{int k = M - 1;// 前置0不打印输出while (k && !a[k])k--;for (int i = k; i >= 0; i--)printf("%lld", a[i]);printf("\n");
}/*通过这个题目，再次学习了以下知识点：1、在C++中，数组作为参数传递给函数时，是引用类型的参数传递2、在C++中，当你使用memcpy函数复制long long类型的数据时，它会按照字节的顺序进行复制，对于每一位字节，会先复制低位字节，然后再复制高位字节3、在C++中，如果两个int类型的整数相乘的结果会溢出，则要先把int类型的整数改成long long类型，然后再进行相乘4、在C++的条件表达式中，除了0以外的所有整数都视为true
*/
int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &w[i]);// 按区间长度从小到大进行遍历// 区间长度从3开始，是因为至少要有三个结点才能构成一个三角形，才有意义for (int len = 3; len <= n; len++)// 遍历当前区间长度的左边界for (int l = 1; l + len - 1 <= n; l++){int r = l + len - 1;// 右边界// 表示当前状态表示的（高精度）值为：10000 00000 00000 00000 00000 00000 00000，相当于正无穷f[l][r][M - 1] = 1;// 状态计算for (int k = l + 1; k < r; k++){LL temp[M];memset(temp, 0, sizeof temp);// 局部变量要赋值，否则存储的是随机值，会影响计算temp[0] = w[l];// 状态计算：f[L,R]=min(f[L,K]+f[K,R]+w[L]*w[K]*w[R])mul(temp, w[k]);mul(temp, w[r]);add(temp, f[l][k]);add(temp, f[k][r]);if (cmp(f[l][r], temp) > 0)memcpy(f[l][r], temp, sizeof temp);}}// 输出结果    res_printf(f[1][n]);return 0;
}

知识点补充

通过这个题目，再次学习了以下知识点：
- 1、在C++中，数组作为参数传递给函数时，是引用类型的参数传递
- 2、在C++中，当你使用memcpy函数复制long long类型的数据时，它会按照字节的顺序进行复制，对于每一位字节，会先复制低位字节，然后再复制高位字节
- 3、在C++中，如果两个int类型的整数相乘的结果会溢出，则要先把int类型的整数改成long long类型，然后再进行相乘
- 4、在C++的条件表达式中，除了0以外的所有整数都视为true

棋盘分割

#include <iostream>
#include <cstring>
#include <cmath>using namespace std;const int K = 15;int k;
int s[9][9];// 这是一个8*8的矩形棋盘
double f[9][9][9][9][K];// 状态表示
double k_average;// 根据题意，得到均方差
double get(int x1, int y1, int x2, int y2)
{double sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] - k_average;return sum * sum / k;
}double dp(int x1, int y1, int x2, int y2, int k)
{double &t = f[x1][y1][x2][y2][k];// 当一个变量名太长时，可以通过这种方式给变量名起个别名，变量的类型要保持一致// 当f[x1][y1][x2][y2][k]不等于-1时，则表明已经计算过f[x1][y1][x2][y2][k]的最小值，无需再进行计算，减少程序运行时间if (t != -1)return t;if (k == 1)return get(x1, y1, x2, y2);t = 0x3f3f3f3f;// 把f[x1][y1][x2][y2][k]初始化为一个很大的值，是为了求f[x1][y1][x2][y2][k]的最小值for (int i = x1; i < x2; i++)// 枚举横着切的情况{// 拿走上方的矩形棋盘，继续递归处理下方的矩形棋盘t = min(t, get(x1, y1, i, y2) + dp(i + 1, y1, x2, y2, k - 1));// 拿走下方的矩形棋盘，继续递归处理上方的矩形棋盘t = min(t, get(i + 1, y1, x2, y2) + dp(x1, y1, i, y2, k - 1));}for (int j = y1; j < y2; j++)// 枚举竖着切的情况{// 拿走左方的矩形棋盘，继续递归处理右方的矩形棋盘t = min(t, get(x1, y1, x2, j) + dp(x1, j + 1, x2, y2, k - 1));// 拿走右方的矩形棋盘，继续递归处理左方的矩形棋盘t = min(t, get(x1, j + 1, x2, y2) + dp(x1, y1, x2, j, k - 1));}return t;
}/*通过这个题目，再次学习了以下知识点：1、double类型在计算机中是通过IEEE754标准来存储的，这是一种用于浮点数表示的标准，IEEE754标准定义了浮点数的存储格式、数值范围和精度，在IEEE754标准中，一个double类型的浮点数占用64位（8字节）内存空间，其中：第1位是符号位（0表示正数，1表示负数）接下来的11位是指数部分最后的52位是尾数（也称为有效数字）2、使用memset函数来初始化double类型的数组是不正确的做法，正确的做法是使用循环来遍历数组并设置每个元素的值
*/
int main()
{scanf("%d", &k);// 把8*8的矩形棋盘，分割成k块矩形棋盘for (int i = 1; i <= 8; i++)for (int j = 1; j <= 8; j++){scanf("%d", &s[i][j]);// 二维前缀和s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];}// 根据题意，得到平均值k_average = (double)s[8][8] / k;// 注意，两个整数相除，结果为整数，需要手动转成浮点数// 使用memset函数来初始化double类型的数组是不正确的做法，正确的做法是使用循环来遍历数组并设置每个元素的值for (int i = 1; i <= 8; i++)for (int j = 1; j <= 8; j++)for (int a = 1; a <= 8; a++)for (int b = 1; b <= 8; b++)for (int v = 1; v <= k; v++)f[i][j][a][b][v] = -1;// 用于记忆化搜索printf("%.3lf\n", sqrt(dp(1, 1, 8, 8, k)));// 采用记忆化搜索的方式，解决DP问题return 0;
}

知识点补充

通过这个题目，再次学习了以下知识点：
- 1、double类型在计算机中是通过IEEE754标准来存储的，这是一种用于浮点数表示的标准，IEEE754标准定义了浮点数的存储格式、数值范围和精度，在IEEE754标准中，一个double类型的浮点数占用64位（8字节）内存空间，其中：
  - 第1位是符号位（0表示正数，1表示负数）
  - 接下来的11位是指数部分
  - 最后的52位是尾数（也称为有效数字）
- 2、使用memset函数来初始化double类型的数组是不正确的做法，正确的做法是使用循环来遍历数组并设置每个元素的值

树的最长路径

#include <iostream>
#include <cstring>using namespace std;const int N = 1e4 + 10;
const int M = N * 2;int n;
int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int w[M];// 存储第idx条边的权值
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条
int ans;// 存储树的一条直径的长度void add(int a, int b, int c)// 插入一条a节点指向b节点的边，c为边的权值
{w[idx] = c;e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}int dfs(int u, int father)// father为u节点的父节点
{int dist = 0;// 存储从u节点出发，一直往下走所能经过的第一长的路径的长度int d1 = 0;// 存储从u节点出发，一直往下走所能经过的第一长的路径的长度int d2 = 0;// 存储从u节点出发，一直往下走所能经过的第二长的路径的长度// 遍历u节点的所有出边for (int i = h[u]; i != -1; i = ne[i]){// 因为此图为无向图，加上此判断，是为了防止在dfs操作的过程中发生死循环if (e[i] == father)continue;// 递归进行dfs操作，w[i]为u节点和其当前子节点的边的权值int t = dfs(e[i], u) + w[i];dist = max(dist, t);// 存储从u节点出发，一直往下走所能经过的第一长的路径的长度if (t > d1)// 更新从u节点出发，一直往下走所能经过的第一长和第二长的路径的长度{d2 = d1;d1 = t;}else if (t > d2)// 更新从u节点出发，一直往下走所能经过的第二长的路径的长度d2 = t;}ans = max(ans, d1 + d2);return dist;
}// 注意：当这棵树的所有边的权值全为负数时，此时只选一个点，不选边，树的一条直径的长度为0
int main()
{scanf("%d", &n);// 初始化每个节点对应的单链表的表头所指向的idx为-1，表示每个节点与其它节点都不直接相连memset(h, -1, sizeof h);for (int i = 1; i <= n - 1; i++){int a, b, c;scanf("%d %d %d", &a, &b, &c);// 无向图add(a, b, c);add(b, a, c);}/*先随便找一个节点作为整棵树的根节点（这个根节点也是dfs操作的起点），然后按照整棵树的高度依次往下，每个节点（包括根节点）都可以视为是树中的某些路径所经过的所有节点中高度最高的节点，据此，即可把树中的所有路径按照节点进行分类，通过dfs操作，枚举每一个节点，相当于枚举树中的所有路径，最终可以找到树的一条直径的长度*/// 把第一个节点作为整棵树的根节点，根节点的父节点视为无，可设置成一个无效值-1，然后开始进行dfs操作dfs(1, -1);printf("%d\n", ans);return 0;
}

树的中心

#include <iostream>
#include <cstring>using namespace std;const int N = 1e4 + 10;
const int M = N * 2;int n;
int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int w[M];// 存储第idx条边的权值
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条
int d1[N];// 存储从u节点出发，一直往下走所能经过的第一长的路径的长度
int d2[N];// 存储从u节点出发，一直往下走所能经过的第二长的路径的长度
int p1[N];// 存储从u节点出发，一直往下走所能经过的第一长的路径对应所经过的子节点的编号
int u1[N];// 存储从u节点出发，先往上走所能经过的第一长的路径的长度
bool is_leaf[N];// 存储u节点是否为无法再继续往下走的节点void add(int a, int b, int c)// 插入一条a节点指向b节点的边，c为边的权值
{w[idx] = c;e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}int dfs_d(int u, int father)// father为u节点的父节点
{d1[u] = d2[u] = -0x3f3f3f3f;// 遍历u节点的所有出边for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];// 因为此图为无向图，加上此判断，是为了防止在dfs操作的过程中发生死循环if (j == father)continue;// 递归进行dfs操作，w[i]为u节点和其当前子节点的边的权值int t = dfs_d(j, u) + w[i];if (t > d1[u]){// 更新从u节点出发，一直往下走所能经过的第一长和第二长的路径的长度d2[u] = d1[u];d1[u] = t;// 更新从u节点出发，一直往下走所能经过的第一长的路径对应所经过的子节点的编号p1[u] = j;}else if (t > d2[u])// 更新从u节点出发，一直往下走所能经过的第二长的路径的长度d2[u] = t;}// 判断u节点是否为无法再继续往下走的节点if (d1[u] == -0x3f3f3f3f){d1[u] = d2[u] = 0;is_leaf[u] = true;}return d1[u];
}void dfs_u(int u, int father)// father为u节点的父节点
{// 遍历u节点的所有出边for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];// 因为此图为无向图，加上此判断，是为了防止在dfs操作的过程中发生死循环if (j == father)continue;// 通过u节点的信息，确定j节点的信息if (p1[u] == j)u1[j] = max(u1[u], d2[u]) + w[i];// w[i]为u节点和其当前子节点（j节点）的边的权值elseu1[j] = max(u1[u], d1[u]) + w[i];// w[i]为u节点和其当前子节点（j节点）的边的权值// 递归进行dfs操作dfs_u(j, u);}
}int main()
{scanf("%d", &n);// 初始化每个节点对应的单链表的表头所指向的idx为-1，表示每个节点与其它节点都不直接相连memset(h, -1, sizeof h);for (int i = 1; i <= n; i++){int a, b, c;scanf("%d %d %d", &a, &b, &c);// 无向图add(a, b, c);add(b, a, c);}/*先随便找一个节点作为整棵树的根节点（这个根节点也是dfs操作的起点），然后按照整棵树的高度依次往下，每个节点（包括根节点）都可以视为是一直往下走或者先往上走的这两种类型的路径的起始节点，据此，即可把树中的所有路径按照节点进行分类，通过dfs操作，枚举每一个节点，相当于枚举树中的所有路径，最终可以在树中找到一个节点，使得该节点到树中其它节点的最大值是其余节点到树中其它节点的最大值中的最小值*//*先确定每个节点所对应的一直往下走所能经过的第一长和第二长的路径的长度（通过子节点的信息，确定父节点的信息）  */dfs_d(1, -1);// 把第一个节点作为整棵树的根节点，根节点的父节点视为无，可设置成一个无效值-1，然后开始进行dfs操作/*然后再确定每个节点所对应的先往上走所能经过的第一长的路径的长度（通过父节点的信息，确定子节点的信息）*/dfs_u(1, -1);// 把第一个节点作为整棵树的根节点，根节点的父节点视为无，可设置成一个无效值-1，然后开始进行dfs操作int res = 0x3f3f3f3f;for (int i = 1; i <= n; i++)if (is_leaf[i])res = min(res, u1[i]);else res = min(res, max(d1[i], u1[i]));// 输出结果printf("%d\n", res);return 0;
}

数字转换

#include <iostream>
#include <cstring>using namespace std;const int N = 5e4 + 10;
const int M = N;int n;
int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条
int sum[N];// 存储每个数的约数之和
bool st[N];// 存储当前节点是否为根节点
int ans;void add(int a, int b)// 插入一条a节点指向b节点的边
{e[idx] = b;ne[idx]= h[a];h[a] = idx++;
}int dfs(int u)
{int d1 = 0;// 存储从u节点出发，一直往下走所能经过的第一长的路径的长度int d2 = 0;// 存储从u节点出发，一直往下走所能经过的第二长的路径的长度// 遍历u节点的所有出边for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];// 递归进行dfs操作，u节点和其当前子节点的边的权值为1int t = dfs(j) + 1;if (t > d1)// 更新从u节点出发，一直往下走所能经过的第一长和第二长的路径的长度{d2 = d1;d1 = t;}else if (t > d2)// 更新从u节点出发，一直往下走所能经过的第二长的路径的长度d2 = t;}ans = max(ans, d1 + d2);return d1;
}int main()
{scanf("%d", &n);// 计算每个数的约数之和，这种做法可以降低时间复杂度for (int i = 1; i <= n; i++)for (int j = 2; i * j <= n; j++)// 因为题目规定每个数的约数不包括它本身，所以j要从2开始sum[i * j] += i;// 初始化每个节点对应的单链表的表头所指向的idx为-1，表示每个节点与其它节点都不直接相连memset(h, -1, sizeof h);for (int i = 2; i <= n; i++)// 因为题目规定所有数字变换在不超过n的正整数范围内进行，所以j要从2开始if (sum[i] < i){// 因为每个数的约数之和只有一个，所以把每个数当作子节点，把每个数的约数之和当作父节点add(sum[i], i);st[i] = true;}// 因为可能存在不止一棵树for (int i = 1; i <= n; i++)// 从每棵树的根节点开始进行dfs操作if (!st[i])dfs(i);// 输出结果printf("%d\n", ans);return 0;
}

二叉苹果树

#include <iostream>
#include <cstring>using namespace std;const int N = 100 + 10;
const int M = N * 2;int n;
int m;
int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int w[M];// 存储第idx条边的权值
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条
int f[N][M];// 状态表示void add(int a, int b, int c)// 插入一条a节点指向b节点的边，c为边的权值
{w[idx] = c;e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}void dfs(int u, int father)
{/*可以把若干个子节点看成若干组物品，每组物品中根据给当前子节点分配的不同的树枝数量对应有不同的物品，即可视为每组物品中有若干件物品，每件物品可能有不同的价值（因为给当前子节点分配的不同的树枝数量，可能会对应得到不同的苹果总数量），每一组物品中最多只能选一件物品（因为每个子节点只能选一次）此时的思路可以用分组背包问题去考虑，结合分组背包问题的状态表示去理解，实际操作和用一维数组去优化分组背包问题的解题过程相似，此时，f[u][j]的第二维度，等同于，用一维数组去优化分组背包问题的解题过程中的一维数组*//*此时的思路可以用分组背包问题去考虑，结合分组背包问题的状态表示去理解，实际操作和用一维数组去优化分组背包问题的解题过程相似，此时，f[u][j]的第二维度，等同于，用一维数组去优化分组背包问题的解题过程中的一维数组*/for (int i = h[u]; i != -1; i = ne[i])// 依次遍历每组物品（循环物品组）{// 因为此图为无向图，加上此判断，是为了防止在dfs操作的过程中发生死循环if (e[i] == father)continue;// 要结合树形DP进行分析，所以要先进行递归操作dfs(e[i], u);for (int j = m; j >= 0; j--)// 树枝数量从大到小循环（循环树枝数量）/*每组物品中根据给当前子节点分配的不同的树枝数量对应有不同的物品，即可视为每组物品中有若干件物品，每件物品可能有不同的价值（因为给当前子节点分配的不同的树枝数量，可能会对应得到不同的苹果总数量），每一组物品中最多只能选一件物品（因为每个子节点只能选一次）*/// 需要思考分析一下，当j等于0时和当j等于1时，第三层循环会如何进行for (int k = 0; k < j; k++)// 遍历给当前子节点分配的树枝数量（循环决策）f[u][j] = max(f[u][j], f[u][j - 1 - k] + w[i] + f[e[i]][k]);// 注意，通过dfs操作回溯后，这里的f[e[i]][k]是本题目状态表示的含义}
}// 这道题目的思路可以参考有依赖的背包问题的思路，进行分析
int main()
{scanf("%d %d", &n, &m);// 初始化每个节点对应的单链表的表头所指向的idx为-1，表示每个节点与其它节点都不直接相连memset(h, -1, sizeof h);for (int i = 1; i <= n - 1; i++){int a, b, c;scanf("%d %d %d", &a, &b, &c);// 无向图add(a, b, c);add(b, a, c);}// 题目规定根节点的编号为1，根节点的父节点视为无，可设置成一个无效值-1，然后开始进行dfs操作dfs(1, -1);// 输出结果printf("%d\n", f[1][m]);return 0;
}

战略游戏

#include <iostream>
#include <cstring>using namespace std;const int N = 1500 + 10;
const int M = N;int n;
int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条边
int f[N][2];// 状态表示
bool st[N];void add(int a, int b)// 插入一条a结点指向b结点的边
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}void dfs(int u)
{// 根据状态表示的含义可得f[u][1] = 1;f[u][0] = 0;// 遍历u结点的所有出边for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];dfs(j);// 递归处理// 状态计算f[u][1] += min(f[j][1], f[j][0]);f[u][0] += f[j][1];}
}int main()
{while (scanf("%d", &n) != -1)// 当scanf没有读到值时，会返回-1{// 初始化每个结点对应的单链表的表头所指向的idx为-1，表示每个结点与其它结点都不直接相连memset(h, -1, sizeof h);idx = 0;memset(st, 0, sizeof st);while (n--){int father, cnt;scanf("%d:(%d)", &father, &cnt);while (cnt--){int son;scanf("%d", &son);add(father, son);st[son] = true;}}int root = 0;// 找到根结点while (st[root])root++;// 从根结点开始进行，状态计算dfs(root);// 输出结果printf("%d\n", min(f[root][1], f[root][0]));}return 0;
}

皇宫看守

#include <iostream>
#include <cstring>using namespace std;const int N = 1500 + 10;
const int M = N;int n;
int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int w[N];// 存储每个节点的费用
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条
int f[N][3];// 状态表示
bool st[N];void add(int a, int b)// 插入一条a结点指向b结点的边
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}void dfs(int u)
{// 根据状态表示的含义可得f[u][2] = w[u];f[u][0] = 0;// 遍历u结点的所有出边for (int i = h[u]; ~i; i = ne[i])// ~i和i!=-1的逻辑判断是一样的{int j = e[i];dfs(j);// 递归处理// 状态计算f[u][0] += min(f[j][1], f[j][2]);// f[root][0]在最终输出结果时，并没有用上，所以没有必要对根结点进行特殊处理f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);}// 当最终递归到叶子结点时，叶子结点并没有子结点，因此可以把f[叶子结点][1]的值赋值为无穷大f[u][1] = 0x3f3f3f3f;// 遍历u结点的所有出边for (int i = h[u]; ~i; i = ne[i]){int j = e[i];// 状态计算f[u][1] = min(f[u][1], f[j][2] + f[u][0] - min(f[j][1], f[j][2]));}
}int main()
{// 初始化每个结点对应的单链表的表头所指向的idx为-1，表示每个结点与其它结点都不直接相连memset(h, -1, sizeof h);scanf("%d", &n);while (n--){int father, temp, cnt;scanf("%d %d %d", &father, &temp, &cnt);w[father] = temp;while (cnt--){int son;scanf("%d", &son);add(father, son);st[son] = true;}}int root = 1;// 找到根结点while (st[root])root++;// 从根结点开始进行，状态计算dfs(root);// 输出结果printf("%d\n", min(f[root][1], f[root][2]));return 0;
}

度的数量

#include <iostream>
#include <vector>using namespace std;const int N = 35;int l, r, k, p;
int c[N][N];/*在组合数问题中，我们把从n个不同元素中选出m个元素的组合数，用C(n,m)表示组合数公式中，有一个常用的递推公式：C(n,m)=C(n-1,m)+C(n-1,m-1)举个例子理解这个递推公式：1、现在有n个苹果，在这n个苹果中只存在1个红色苹果，求在n个苹果中选出m个苹果的组合数2、在n个苹果中选出m个苹果可以分为两种情况，第一种情况为选出的m个苹果中不包含红色苹果，第二种情况为选出的m个苹果中包含红色苹果3、在n个苹果中选出m个苹果的组合数（C(n,m)）=先去掉不选的1个红色苹果，在剩下的n-1个苹果中选出m个苹果（C(n-1,m)）+先去掉已选出的1个红色苹果，在剩下的n-1个苹果中选出m-1个苹果（C(n-1,m-1)）
*/
void init()
{for (int i = 0; i < N; i++)for (int j = 0; j <= i; j++)if (!j)c[i][j] = 1;// 当j为0时，则表示从i个不同元素中选出0个元素的组合数，此时组合数为1else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}int dp(int n)
{vector<int> num;// 把n看成p进制数，然后把n中从低位到高位的每一位数字依次放入到num数组中while (n){num.push_back(n % p);n /= p;}int res = 0;int before = 0;// 记录在前面的位置中，已经填了1的位置的个数for (int i = num.size() - 1; i >= 0; i--){int x = num[i];// 只有当当前位上的数大于0时，才存在在当前位上选择填0的情况if (x > 0){// 当在当前位上选择填0时，对应满足条件的数的个数为从剩下i个不同位置中选出k-before个位置填1的组合数res += c[i][k - before];/*当当前位上的数等于1时，如果在当前位上不选择填0的话，那么在当前位上只能选择填1，且后面的位置暂时无法确定选择填什么数，因为要确保是在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数*/if (x == 1){before++;if (before > k)break;}/*当当前位上的数大于1时，如果在当前位上不选择填0的话，那么当在当前位上选择填1时，对应满足条件的数的个数为从剩下i个不同位置中选出k-before-1个位置填1的组合数*/if (x > 1){if (k - before - 1 >= 0)res += c[i][k - before - 1];break;}}// 不要遗漏特殊情况if (!i && k == before)res++;}return res;
}int main()
{// 根据递推公式，先求出所有情况所对应的组合数init();scanf("%d %d %d %d", &l, &r, &k, &p);/*dp(r)表示在1~r中，满足条件的数的个数，dp(l)表示在1~l中，满足条件的数的个数，dp(r)-dp(l-1)表示在l~r中，满足条件的数的个数*/printf("%d\n", dp(r) - dp(l - 1));return 0;
}

数字游戏

#include <iostream>
#include <vector>using namespace std;const int N = 15;int l, r;
int f[N][10];// 状态表示void init()
{// 根据状态表示可得for (int j = 1; j <= 9; j++)// 因为0不算，所以j从1开始f[1][j] = 1;// 状态计算for (int i = 2; i < N; i++)for (int j = 0; j <= 9; j++)for (int k = j; k <= 9; k++)f[i][j] += f[i - 1][k];
}int dp(int n)
{vector<int> num;// 先把n中从低位到高位的每一位数字依次放入到num数组中while (n){num.push_back(n % 10);n /= 10;}int res = 0;int before = 0;// 记录上一个位置的数字for (int i = num.size() - 1; i >= 0; i--){int x = num[i];if (before > x)// 当无法继续在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数时，直接退出循环即可break;/*当当前位上的数取值为[before,x-1]时，则对应满足条件的数的个数可以直接通过状态表示的值得到*/for (int j = before; j <= x - 1; j++)res += f[i + 1][j];/*当当前位上的数取值为x时，则后面的位置暂时无法确定取值为什么数，因为要确保是在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数*/before = x;// 不要遗漏特殊情况if (!i)res++;}return res;
}int main()
{// 根据递推公式，先求出所有情况所对应的组合数init();while (~scanf("%d %d", &l, &r))/*dp(r)表示在1~r中，满足条件的数的个数，dp(l)表示在1~l中，满足条件的数的个数，dp(r)-dp(l-1)表示在l~r中，满足条件的数的个数*/printf("%d\n", dp(r) - dp(l - 1));return 0;
}

Windy数

#include <iostream>
#include <vector>
#include <cmath>using namespace std;const int N = 15;int l, r;
int f[N][10];// 状态表示void init()
{// 根据状态表示可得for (int j = 0; j <= 9; j++)// 这里要从0开始，不然会遗漏某些情况f[1][j] = 1;// 状态计算for (int i = 2; i < N; i++)for (int j = 0; j <= 9; j++)for (int k = 0; k <= 9; k++)if (abs(j - k) >= 2)f[i][j] += f[i - 1][k];
}int dp(int n)
{vector<int> num;// 先把n中从低位到高位的每一位数字依次放入到num数组中while (n){num.push_back(n % 10);n /= 10;}int res = 0;int before = -1;// 记录上一个位置的数字for (int i = num.size() - 1; i >= 0; i--){int x = num[i];/*当当前位为最高位时，则最高位从1开始，计算对应满足条件的数的个数*/for (int j = (i == (num.size() - 1)); j < x; j++)if (abs(j - before) >= 2)res += f[i + 1][j];if (abs(x - before) < 2)// 当无法继续在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数时，直接退出循环即可break;/*当当前位上的数取值为x时，则后面的位置暂时无法确定取值为什么数，因为要确保是在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数*/before = x;// 不要遗漏特殊情况if (!i)res++;}// 处理前导0的情况，计算对应满足条件的数的个数for (int i = num.size () - 1; i >= 1; i--)for (int j = 1; j <= 9; j++)res += f[i][j];return res;
}int main()
{// 根据递推公式，先求出所有情况所对应的组合数init();scanf("%d %d", &l, &r);/*dp(r)表示在1~r中，满足条件的数的个数，dp(l)表示在1~l中，满足条件的数的个数，dp(r)-dp(l-1)表示在l~r中，满足条件的数的个数*/printf("%d\n", dp(r) - dp(l - 1));return 0;
}

数字游戏 II

#include <iostream>
#include <cstring>
#include <vector>using namespace std;const int N = 15;
const int M = 110;int l, r, p;
int f[N][10][M];// 状态表示int mod(int a, int p)
{/*在C++中，计算x % N，如果x为负数则余数为负数，x为正数则余数为正数(x % N + N) % N的目的就是为了让x % N的结果一定变为正数*/return (a % p + p) % p;
}void init()
{// 根据状态表示可得for (int j = 0; j <= 9; j++)// 这里要从0开始，不然会遗漏某些情况f[1][j][mod(j, p)] = 1;// 状态计算for (int i = 2; i < N; i++)for (int j = 0; j <= 9; j++)for (int k = 0; k < p; k++)for (int x = 0; x <= 9; x++)f[i][j][k] += f[i - 1][x][mod(k - j, p)];
}int dp(int n)
{if (!n)return 1;vector<int> num;// 先把n中从低位到高位的每一位数字依次放入到num数组中while (n){num.push_back(n % 10);n /= 10;}int res = 0;int before = 0;// 记录在前面的所有位置上的数字之和for (int i = num.size() - 1; i >= 0; i--){int x = num[i];/*当当前位上的数取值为[0,x-1]时，则对应满足条件的数的个数可以直接通过状态表示的值得到*/for (int j = 0; j < x; j++)res += f[i + 1][j][mod(0 - before, p)];/*当当前位上的数取值为x时，则后面的位置暂时无法确定取值为什么数，因为要确保是在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数*/before += x;// 不要遗漏特殊情况if (!i && mod(before, p) == 0)res++;}return res;
}int main()
{while (~scanf("%d %d %d", &l, &r, &p)){memset(f, 0, sizeof f);// 根据递推公式，先求出所有情况所对应的组合数init();/*dp(r)表示在1~r中，满足条件的数的个数，dp(l)表示在1~l中，满足条件的数的个数，dp(r)-dp(l-1)表示在l~r中，满足条件的数的个数*/printf("%d\n", dp(r) - dp(l - 1));}return 0;
}

不要62

#include <iostream>
#include <cstring>
#include <vector>using namespace std;const int N = 15;int f[N][10];// 状态表示
int l, r;void init()
{// 根据状态表示可得for (int j = 0; j <= 9; j++)// 这里要从0开始，不然会遗漏某些情况if (j != 4)f[1][j] = 1;// 状态计算for (int i = 2; i < N; i++)for (int j = 0; j <= 9; j++)if (j != 4)for (int k = 0; k <= 9; k++){if (k == 4 || (j == 6 && k == 2))continue;f[i][j] += f[i - 1][k];}
}int dp(int n)
{if (!n)return 1;vector<int> num;// 先把n中从低位到高位的每一位数字依次放入到num数组中while (n){num.push_back(n % 10);n /= 10;}int res = 0;int before = 0;// 记录上一个位置的数字for (int i = num.size() - 1; i >= 0; i--){int x = num[i];/*当当前位上的数取值为[0,x-1]时，则对应满足条件的数的个数可以直接通过状态表示的值得到*/for (int j = 0; j <= x - 1; j++){if (j == 4 || (before == 6 && j == 2))continue;res += f[i + 1][j];}if (x == 4 || (before == 6 && x == 2))// 当无法继续在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数时，直接退出循环即可break;/*当当前位上的数取值为x时，则后面的位置暂时无法确定取值为什么数，因为要确保是在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数*/before = x;// 不要遗漏特殊情况if (!i)res++;}return res;
}int main()
{while (scanf("%d %d", &l, &r), l || r)// 也可以这么写，这个叫逗号表达式。逗号表达式的真假只等于最后一个数的真假{memset(f, 0, sizeof f);// 根据递推公式，先求出所有情况所对应的组合数init();/*dp(r)表示在1~r中，满足条件的数的个数，dp(l)表示在1~l中，满足条件的数的个数，dp(r)-dp(l-1)表示在l~r中，满足条件的数的个数*/printf("%d\n", dp(r) - dp(l - 1));}return 0;
}

恨7不成妻

#include <iostream>
#include <cstring>
#include <vector>using namespace std;typedef long long LL;const int N = 19;
const int P = 1e9 + 7;struct F
{int s0 = 0;// 所有满足条件的数的0次方的和int s1 = 0;// 所有满足条件的数的1次方的和int s2 = 0;// 所有满足条件的数的2次方的和
}f[N][10][7][7];// 状态表示
int power7[N];// 存储10的i次方模7的结果
int powerP[N];// 存储10的i次方模P的结果int mod(LL a, int p)
{/*在C++中，计算x % N，如果x为负数则余数为负数，x为正数则余数为正数(x % N + N) % N的目的就是为了让x % N的结果一定变为正数*/return (a % p + p) % p;
}void init()
{// 根据状态表示可得for (int j = 0; j <= 9; j++)// 这里要从0开始，不然会遗漏某些情况if (j != 7){F &v = f[1][j][j % 7][j % 7];v.s0 = 1;v.s1 = j;v.s2 = j * j;}LL power = 10;// 状态计算for (int i = 2; i < N; i++, power *= 10)for (int j = 0; j <= 9; j++)if (j != 7)for (int a = 0; a < 7; a++)for (int b = 0; b < 7; b++)for (int k = 0; k <= 9; k++)if (k != 7){F &v1 = f[i][j][a][b];F &v2 = f[i - 1][k][mod(a - j * power, 7)][mod(b - j, 7)];// 在C++中，一个int类型的整数和一个long long类型的整数相乘时，它们相乘的结果的类型为long long类型// 一定要注意取模的技巧，即要把long long类型的结果的范围及时限制在0~(P-1)的范围内，然后再继续进行计算v1.s0 = mod(v1.s0 + v2.s0, P);v1.s1 = mod(v1.s1 + j * power % P * v2.s0 + v2.s1, P);v1.s2 = mod(v1.s2 + j * j * (power % P) % P * (power % P) % P * v2.s0 + v2.s2 + 2 * j * (power % P) % P * v2.s1,P);}
}/*返回，在，由，一共有i位且最高位为j且所有位置上的数字不包含7且这个整数模7的结果不为a且所有位置上的数字之和模7的结果不为b，组成的集合，中，的每个数的0次方的和、与每个数的1次方的和、与每个数的2次方的和
*/
F get(int i, int j, int a, int b)
{int s0 = 0;// 所有满足条件的数的0次方的和int s1 = 0;// 所有满足条件的数的1次方的和int s2 = 0;// 所有满足条件的数的2次方的和for (int x = 0; x < 7; x++)for (int y = 0; y < 7; y++)if (x != a && y != b){F &v = f[i][j][x][y];s0 = (s0 + v.s0) % P;s1 = (s1 + v.s1) % P;s2 = (s2 + v.s2) % P;}return {s0, s1, s2};
}int dp(LL n)
{if (!n)return 0;LL backup_n = n;vector<int> num;// 先把n中从低位到高位的每一位数字依次放入到num数组中while (n){num.push_back(n % 10);n /= 10;}int res = 0;LL before_a = 0;// 记录在前面的所有位置上的数字所组成的整数int before_b = 0;// 记录在前面的所有位置上的数字之和for (int i = num.size() - 1; i >= 0; i--){int x = num[i];/*当当前位上的数取值为[0,x-1]时，则对应满足条件的数的平方和可以结合状态表示分析得到*/for (int j = 0; j < x; j++)if (j != 7){F v = get(i + 1, j, mod(0 - before_a * power7[i + 1], 7), mod(0 - before_b, 7));// 在C++中，一个int类型的整数和一个long long类型的整数相乘时，它们相乘的结果的类型为long long类型// 一定要注意取模的技巧，即要把long long类型的结果的范围及时限制在0~(P-1)的范围内，然后再继续进行计算res = mod(res + (before_a % P) * (before_a % P) % P * powerP[i + 1] % P * powerP[i + 1] % P * v.s0 + v.s2 + 2 * (before_a % P) * powerP[i + 1] % P * v.s1, P);}// 当无法继续在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数时，直接退出循环即可if (x == 7)break;/*当当前位上的数取值为x时，则后面的位置暂时无法确定取值为什么数，因为要确保是在1~n中（不能超过1~n的范围）计算对应满足条件的数的个数*/before_a = before_a * 10 + x;before_b += x;// 不要遗漏特殊情况if (!i && before_a % 7 && before_b % 7)res = (res + (backup_n % P) * (backup_n % P)) % P;}return res;
}int main()
{int n;scanf("%d", &n);while (n--){memset(f, 0, sizeof f);// 初始化处理init();power7[0] = 1;// 计算10的i次方模7的结果for (int i = 1; i < N; i++)power7[i] = power7[i - 1] * 10 % 7;powerP[0] = 1;// 计算10的i次方模P的结果for (int i = 1; i < N; i++)// 在C++中，如果两个int类型的整数相乘的结果会溢出，则要先把int类型的整数改成long long类型，然后再进行相乘powerP[i] = (LL)powerP[i - 1] * 10 % P;LL l, r;scanf("%lld %lld", &l, &r);/*dp(r)表示在1~r中，满足条件的数的个数，dp(l)表示在1~l中，满足条件的数的个数，dp(r)-dp(l-1)表示在l~r中，满足条件的数的个数*/// 因为dp函数中返回的结果是经过取模后的结果，所以可能存在dp(r)<dp(l-1)的情况，所以需要使用mod函数进行取模printf("%d\n", mod(dp(r) - dp(l - 1), P));}return 0;
}

知识点补充

在C++中，如果两个int类型的整数相乘的结果会溢出，则要先把int类型的整数改成long long类型，然后再进行相乘
在C++中，一个int类型的整数和一个long long类型的整数相乘时，它们相乘的结果的类型为long long类型
在C++中，两个不同整数类型的数的相乘结果会自动提升为更高精度的类型，以防止数据丢失

最大子序和

#include <iostream>
#include <limits.h>using namespace std;const int N = 3e5 + 10;int s[N];// 前缀和数组
int q[N];// 滑动窗口的数组（用数组模拟队列），这里的q数组记录的值是s数组的下标
int n;
int k;// 滑动窗口的大小int main()
{scanf("%d %d", &n, &k);for (int i = 1; i <= n; i++){scanf("%d", &s[i]);s[i] += s[i - 1];}int res = INT_MIN;// INT_MIN表示int类型的最小值，需要引入头文件limits.h才可以使用// 一开始设定，队头为0，队尾为0，则有hh<=tt，表示队列一开始就不为空int hh = 0, tt = 0;for (int i = 1; i <= n; i++){if (q[hh] < i - k)// 因为s数组是前缀和数组，所以这里是q[hh]<i-k，而不是q[hh]<i-k+1hh++;// 只要保证在s[r]-s[l-1]中的s[l-1]为最小值，即可保证s[r]-s[l-1]的结果取到最大值res = max(res, s[i] - s[q[hh]]);// 当前队列队头对应的s数组的下标的值即为滑动窗口中的最小值// 当队列不为空，且队尾对应的s数组的下标的值大于等于当前遍历到的s[i]，则弹出队尾元素// 保证队列的单调性while (hh <= tt && s[q[tt]] >= s[i])tt--;// 这里的q数组记录的值是s数组的下标q[++tt] = i;}printf("%d\n", res);return 0;
}

修剪草坪

#include <iostream>using namespace std;typedef long long LL;const int N = 1e5 + 10;int n;
int k;// 滑动窗口的大小
LL s[N];// 前缀和数组
LL f[N];// 状态表示
int q[N];// 滑动窗口的数组（用数组模拟队列）LL g(int x)
{if (!x)return 0;return f[x - 1] - s[x];
}int main()
{scanf("%d %d", &n, &k);for (int i = 1; i <= n; i++){scanf("%lld", &s[i]);s[i] += s[i - 1];}// 一开始设定，队头为0，队尾为0，则有hh<=tt，表示队列一开始就不为空int hh = 0, tt = 0;for (int i = 1; i <= n; i++){if (q[hh] < i - k)// 判断队头是否已经超出窗口的范围hh++;// 状态计算f[i] = max(f[i - 1], g(q[hh]) + s[i]);// 保证队列的单调性while (hh <= tt && g(q[tt]) <= g(i))tt--;q[++tt] = i;}// 输出结果printf("%lld\n", f[n]);return 0;
}

旅行问题

#include <iostream>using namespace std;const int N = 2 * 1e6 + 10;// 因为要破环成链，所以是2 * 1e6 + 10int n;
int o[N], d[N];
long long s[N];// 前缀和数组
int q[N];// 滑动窗口的数组（用数组模拟队列），这里的q数组记录的值是s数组的下标
bool st[N];int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d %d", &o[i], &d[i]);// 顺时针for (int i = 1; i <= n; i++)s[i] = s[i + n] = o[i] - d[i];for (int i = 1; i <= 2 * n; i++)s[i] += s[i - 1];int hh = 0, tt = -1;// 一开始设定，队头为0，队尾为-1q[0] = 2 * n - 1;for (int i = 2 * n - 1; i >= 0; i--){if (q[hh] > i + n)// 判断队头对应的s数组的下标是否已经超出窗口的范围hh++;if (i <= n - 1)// 只要保证在s[q[hh]]-s[i]中的s[q[hh]]为最小值，即可保证s[q[hh]]-s[i]的结果取到最小值// 当s[q[hh]]-s[i]的结果取到最小值时，仍然大于等于0，则表示从i+1出发，能朝顺时针方向走一圈回到原点if (s[q[hh]] - s[i] >= 0)st[i + 1] = true;// 当队列不为空，且队尾对应的s数组的下标的值大于等于当前遍历到的s[i]，则弹出队尾元素// 保证队列的单调性while (hh <= tt && s[q[tt]] >= s[i])tt--;q[++tt] = i;// 这里的q数组记录的值是s数组的下标}// 逆时针d[0] = d[n];for (int i = 1; i <= n; i++)s[i] = s[i + n] = o[i] - d[i - 1];for (int i = 1; i <= 2 * n; i++)s[i] += s[i - 1];hh = 0, tt = -1;// 一开始设定，队头为0，队尾为-1q[0] = 1;for (int i = 1; i <= 2 * n; i++){if (q[hh] < i - n)// 判断队头对应的s数组的下标是否已经超出窗口的范围hh++;if (i >= n + 1)// 只要保证在s[i]-s[q[hh]]中的s[q[hh]]为最大值，即可保证s[i]-s[q[hh]]的结果取到最小值// 当s[i]-s[q[hh]]的结果取到最小值时，仍然大于等于0，则表示从i-n出发，能朝逆时针方向走一圈回到原点if (s[i] - s[q[hh]] >= 0)st[i - n] = true;// 当队列不为空，且队尾对应的s数组的下标的值小于等于当前遍历到的s[i]，则弹出队尾元素// 保证队列的单调性while (hh <= tt && s[q[tt]] <= s[i])tt--;q[++tt] = i;// 这里的q数组记录的值是s数组的下标}// 输出结果for (int i = 1; i <= n; i++)if (st[i])printf("TAK\n");elseprintf("NIE\n");return 0;
}

烽火传递

#include <iostream>using namespace std;const int N = 2e6 + 10;int n;
int k;// 滑动窗口的大小
int w[N];
int f[N];
int q[N];// 滑动窗口的数组（用数组模拟队列），这里的q数组记录的值是f数组的下标int main()
{scanf("%d %d", &n, &k);for (int i = 1; i <= n; i++)scanf("%d", &w[i]);// 一开始设定，队头为0，队尾为0，则有hh<=tt，表示队列一开始就不为空int hh = 0, tt = 0;for (int i = 1; i <= n; i++){if (q[hh] < i - k)// 判断队头对应的f数组的下标是否已经超出窗口的范围hh++;// 状态计算f[i] = f[q[hh]] + w[i];// 当前队列队头对应的f数组的下标的值即为滑动窗口中的最小值// 当队列不为空，且队尾对应的f数组的下标的值大于等于当前遍历到的f[i]，则弹出队尾元素// 保证队列的单调性while (hh <= tt && f[q[tt]] >= f[i])tt--;// 这里的q数组记录的值是f数组的下标q[++tt] = i;}int res = 1e9;for (int i = n - k + 1; i <= n; i++)res = min(res, f[i]);// 输出结果    printf("%d\n", res);return 0;
}

绿色通道

#include <iostream>using namespace std;const int N = 5e4 + 10;int n;
int t;
int w[N];
int f[N];
int q[N];// 滑动窗口的数组（用数组模拟队列），这里的q数组记录的值是f数组的下标// 判断最长的空题段在不超过limit且抄上第i个题目的情况下，最少需要花费的代价是否小于等于给定的t
bool check(int limit)// limit为滑动窗口的大小
{// 一开始设定，队头为0，队尾为0，则有hh<=tt，表示队列一开始就不为空int hh = 0, tt = 0;for (int i = 1; i <= n; i++){if (q[hh] < i - limit - 1)// 判断队头对应的f数组的下标是否已经超出窗口的范围hh++;// 状态计算    f[i] = f[q[hh]] + w[i];// 当前队列队头对应的f数组的下标的值即为滑动窗口中的最小值// 当队列不为空，且队尾对应的f数组的下标的值大于等于当前遍历到的f[i]，则弹出队尾元素// 保证队列的单调性while (hh <= tt && f[q[tt]] >= f[i])tt--;// 这里的q数组记录的值是f数组的下标q[++tt] = i;}int res = 1e9;for (int i = n - limit; i <= n; i++)res = min(res, f[i]);// 判断最长的空题段在不超过limit的情况下，最少需要花费的代价是否小于等于给定的t    if (res <= t)return true;elsereturn false;
}int main()
{scanf("%d %d", &n, &t);for (int i = 1; i <= n; i++)scanf("%d", &w[i]);int l = 0;// 二分区间的左边界int r = n;// 二分区间的右边界while (l < r){int mid = (l + r) / 2;if (check(mid))r = mid;// 这里是二分右区间的左端点elsel = mid + 1;}printf("%d\n", r);return 0;
}

理想的正方形

#include <iostream>using namespace std;const int N = 1e3 + 10;int n, m;
int k;// 滑动窗口的大小
int w[N][N];
int row_max[N][N];
int row_min[N][N];
int q[N];// 滑动窗口的数组（用数组模拟队列）// 单调队列求滑动窗口中的最大值
void get_max(int a[], int right_end, int b[])
{int hh = 0, tt = -1;// 一开始设定，队头为0，队尾为-1for (int j = 1; j <= right_end; j++){if (q[hh] <= j - k)// 判断队头是否已经超出窗口的范围hh++;// 保证队列的单调性while (hh <= tt && a[q[tt]] <= a[j])tt--;q[++tt] = j;b[j] = a[q[hh]];}
}// 单调队列求滑动窗口中的最小值
void get_min(int a[], int right_end, int b[])
{int hh = 0, tt = -1;// 一开始设定，队头为0，队尾为-1for (int j = 1; j <= right_end; j++){if (q[hh] <= j - k)// 判断队头是否已经超出窗口的范围hh++;// 保证队列的单调性while (hh <= tt && a[q[tt]] >= a[j])tt--;q[++tt] = j;b[j] = a[q[hh]];}
}int main()
{scanf("%d %d %d", &n, &m, &k);for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)scanf("%d", &w[i][j]);// 处理每一行，每一行分别求出滑动窗口中的最大值、最小值for (int i = 1; i <= n; i++){get_max(w[i], m, row_max[i]);get_min(w[i], m, row_min[i]);}int res = 1e9;int a[n], b[n], c[n];for (int j = k; j <= m; j++)// 这里要从k开始{for (int i = 1; i <= n; i++)a[i] = row_max[i][j];get_max(a, n, b);for (int i = 1; i <= n; i++)a[i] = row_min[i][j];get_min(a, n, c);for (int i = k; i <= n; i++)// 这里要从k开始res = min(res, b[i] - c[i]);}// 输出结果printf("%d\n", res);return 0;
}

任务安排1

#include <iostream>
#include <cstring>using namespace std;typedef long long LL;const int N = 1e5 + 10;int n;
int s;
int sumt[N], sumc[N];
LL f[N];// 状态表示int main()
{scanf("%d %d", &n, &s);for (int i = 1; i <= n; i++){scanf("%d %d", &sumt[i], &sumc[i]);sumt[i] += sumt[i - 1];sumc[i] += sumc[i - 1];}memset(f, 0x3f3f3f3f, sizeof f);f[0] = 0;// 根据状态表示可得// 状态计算for (int i = 1; i <= n; i++)for (int j = 0; j <= i - 1; j++)f[i] = min(f[i], f[j] + (LL)(sumc[i] - sumc[j]) * sumt[i] + (LL)(sumc[n] - sumc[j]) * s);// 输出结果printf("%lld\n", f[n]);return 0;
}

任务安排2

#include <iostream>using namespace std;typedef long long LL;const int N = 3e5 + 10;int n;
int s;
LL t[N], c[N];
LL f[N];// 状态表示
int q[N];int main()
{scanf("%d %d", &n, &s);for (int i = 1; i <= n; i++){scanf("%lld %lld", &t[i], &c[i]);t[i] += t[i - 1];c[i] += c[i - 1];}int hh = 0, tt = 0;q[hh] = 0;// 状态计算的最开始一定是从(c[0],f[0])转移过来的/*状态计算，f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n]，把f[j]看成y，把(t[i]+s)看成k，把c[j]看成x，则有，f[i] = y - k * x + t[i] * c[i] + s * c[n]，继续变形，则有，y = k * x + f[i] - t[i] * c[i] - s * c[n]，把f[i]-t[i]*c[i]-s*c[n]看成b，则有，y = k * x + b，要想让f[i]取到最小值，即让b取到最小值，即让状态计算中的截距取到最小值，此时就要在当前斜率k的情况下，找到穿过前面的哪个点(c[j],f[j])可以让状态计算中的截距取到最小值，通过画图思考分析可以知道，因为斜率k是一直在变大的，所以寻找穿过前面的哪个点(c[j],f[j])的这个过程，可以使用单调队列来优化*/for (int i = 1; i <= n; i++){/*当hh<tt时，则表示可选择穿过的前面的点的数量大于等于2个，通过画图思考分析可以知道，因为斜率k是一直在变大的，所以寻找穿过前面的哪个点(c[j],f[j])的这个过程，可以使用单调队列来优化，把已经不可能再被选择穿过的前面的点(c[j],f[j])及时地干掉即可*/while (hh < tt && (f[q[hh + 1]] - f[q[hh]]) <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]]))hh++;// 在当前斜率k的情况下，穿过前面的这个点(c[q[hh]],f[q[hh]])可以让状态计算中的截距取到最小值int j = q[hh];// 状态计算f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];// 把已经不可能再被选择穿过的前面的点(c[j],f[j])及时地干掉即可while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]]))tt--;q[++tt] = i;}// 输出结果printf("%lld\n", f[n]);return 0;
}

任务安排3

#include <iostream>using namespace std;typedef long long LL;const int N = 3e5 + 10;int n;
int s;
LL t[N], c[N];
LL f[N];// 状态表示
int q[N];int main()
{scanf("%d %d", &n, &s);for (int i = 1; i <= n; i++){scanf("%lld %lld", &t[i], &c[i]);t[i] += t[i - 1];c[i] += c[i - 1];}int hh = 0, tt = 0;q[hh] = 0;// 状态计算的最开始一定是从(c[0],f[0])转移过来的/*状态计算，f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n]，把f[j]看成y，把(t[i]+s)看成k，把c[j]看成x，则有，f[i] = y - k * x + t[i] * c[i] + s * c[n]，继续变形，则有，y = k * x + f[i] - t[i] * c[i] - s * c[n]，把f[i]-t[i]*c[i]-s*c[n]看成b，则有，y = k * x + b，要想让f[i]取到最小值，即让b取到最小值，即让状态计算中的截距取到最小值，此时就要在当前斜率k的情况下，找到穿过前面的哪个点(c[j],f[j])可以让状态计算中的截距取到最小值，通过画图思考分析可以知道，因为斜率k并不是一直在变大的，所以寻找穿过前面的哪个点(c[j],f[j])的这个过程，可以使用二分查找来优化*/for (int i = 1; i <= n; i++){int l = hh, r = tt;/*当hh<tt时，则表示可选择穿过的前面的点的数量大于等于2个，通过画图思考分析可以知道，因为斜率k并不是一直在变大的，所以寻找穿过前面的哪个点(c[j],f[j])的这个过程，可以使用二分查找来优化*/while (l < r){int mid = (l + r) / 2;if ((f[q[mid + 1]] - f[q[mid]]) > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]]))r = mid;elsel = mid + 1;}// 在当前斜率k的情况下，穿过前面的这个点(c[q[r]],f[q[r]])可以让状态计算中的截距取到最小值int j = q[r];// 状态计算f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];// 把已经不可能再被选择穿过的前面的点(c[j],f[j])及时地干掉即可while (hh < tt && (__int128)(f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (__int128)(f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]]))tt--;q[++tt] = i;}// 输出结果printf("%lld\n", f[n]);return 0;
}

知识点补充

在C++中，如果两个long long类型的整数相乘的结果会溢出，则要先把long long类型的整数改成__int128类型，然后再进行相乘

运输小猫

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef long long LL;const int N = 1e5 + 10;
const int M = 1e5 + 10;
const int P = 100 + 10;int n, m, p;
LL d[N];
LL a[M], s[M];
LL f[P][M];// 状态表示
int q[M];LL get_y(int k, int j)
{return f[j - 1][k] + s[k];
}/*解题思路：1、假设某个饲养员的出发时间为S，则该饲养员能把在第i座山上的小猫接走，需要满足的条件为，S>=t-d[i]（其中，t为在第i座山上的小猫的玩耍结束时间，d[i]为在第i座山上的小猫距离1号山的长度）2、假设某个饲养员的出发时间为S，则第i座山上的小猫需要等待的时间为S-(t-d[i])3、一共有m只小猫，把每只小猫对应的t和d[i]所构成的t-d[i]设为a[i]，然后把m个a[i]按照从小到大进行排序，a[1],a[2],a[3],......,a[m]4、根据a[1],a[2],a[3],......,a[m]，可得，假设某个饲养员要接走a[1],a[2],a[3]这三只小猫，则该饲养员最早的出发时间为a[3]，则a[1],a[2],a[3]这三只小猫等待的时间总和为，(a[3]-a[1])+(a[3]-a[2])+(a[3]-a[3])，化简可得，a[3]*(3-0)-(a[1]+a[2]+a[3])5、此时，即可把问题转化为求，让p个饲养员接走m个小猫，m个小猫等待的时间总和，的最小值，根据a[1],a[2],a[3],......,a[m]，可得，状态表示：f[j][i]（f[j][i]表示，在，由，将前i个小猫接走且饲养员的数量不超过j个的每种选法的小猫等待的时间总和，组成的集合，中，的最小值）状态计算：f[j][i]=min(f[j-1][k]+a[i]*(i-k)-(s[i]-s[k]))（其中s数组为a[1],a[2],a[3],......,a[m]的前缀和数组，k∈{0,1,2,...,j-1}）
*/
int main()
{scanf("%d %d %d", &n, &m, &p);for (int i = 2; i <= n; i++){scanf("%lld", &d[i]);d[i] += d[i - 1];}for (int i = 1; i <= m; i++){int h;LL t;scanf("%d %lld", &h, &t);a[i] = t - d[h];}sort(a + 1, a + m + 1);// 从小到大进行排序for (int i = 1; i <= m; i++)s[i] = s[i - 1] + a[i];// 根据状态表示可得for (int i = 1; i <= m; i++)f[0][i] = 0x3f3f3f3f3f3f3f3f;/*状态计算，f[j][i] = f[j - 1][k] + s[k] - a[i] * k + a[i] * i - s[i]，把f[j-1][k]+s[k]看成y，把a[i]看成K（斜率），把k看成x，则有，f[j][i] = y - K * x + a[i] * i - s[i]，继续变形，则有，y = K * x + f[j][i] - a[i] * i + s[i]，把f[j][i]-a[i]*i+s[i]看成b，则有，y = K * x + b，要想让f[j][i]取到最小值，即让b取到最小值，即让状态计算中的截距取到最小值，此时就要在当前斜率K的情况下，找到穿过前面的哪个点(k,f[j-1][k]+s[k])可以让状态计算中的截距取到最小值，通过画图思考分析可以知道，因为斜率K是一直在变大的，所以寻找穿过前面的哪个点(k,f[j-1][k]+s[k])的这个过程，可以使用单调队列来优化*/for (int j = 1; j <= p; j++){int hh = 0, tt = 0;q[hh] = 0;// 状态计算的最开始一定是从(0,f[j-1][0]+s[0])转移过来的for (int i = 1; i <= m; i++){/*当hh<tt时，则表示可选择穿过的前面的点的数量大于等于2个，通过画图思考分析可以知道，因为斜率K是一直在变大的，所以寻找穿过前面的哪个点(k,f[j-1][k]+s[k])的这个过程，可以使用单调队列来优化，把已经不可能再被选择穿过的前面的点(k,f[j-1][k]+s[k])及时地干掉即可*/while (hh < tt && (get_y(q[hh + 1], j) - get_y(q[hh], j)) <= a[i] * (q[hh + 1] - q[hh]))hh++;// 在当前斜率K的情况下，穿过前面的这个点(q[hh],f[j-1][q[hh]]+s[q[hh]])可以让状态计算中的截距取到最小值    int k = q[hh];// 状态计算f[j][i] = f[j - 1][k] + s[k] - a[i] * k + a[i] * i - s[i];// 把已经不可能再被选择穿过的前面的点(k,f[j-1][k]+s[k])及时地干掉即可while (hh < tt && (get_y(q[tt], j) - get_y(q[tt - 1], j)) * (i - q[tt - 1]) >= (get_y(i, j) - get_y(q[tt - 1], j)) * (q[tt] - q[tt - 1]))tt--;q[++tt] = i;}}// 输出结果printf("%lld\n", f[p][m]);return 0;
}