目录

数学

买不到的数目

蚂蚁感冒

 饮料换购

DP

01背包问题

摘花生

最长上升子序列

地宫取宝

波动数列

---

数学

买不到的数目

1205. 买不到的数目 - AcWing题库

这道题的意思就是给定两个正整数p和q，求xp+yq这一个组合不能凑出来的最大正整数是多少
首先我们要知道，当p和q的最大公约数大于1时，是一定无解的。例如2和6，最大公约数是2，也就是说这两个数都是2的倍数，那么大部分2的倍数都是能够被凑出来的，所以无解。但是这道题并不需要考虑这种情况，因为题目中已经明确说明一定有解

当我们分析不出来的时候，我们可以考虑打表找规律

#include<iostream>
using namespace std;bool dfs(int m, int p, int q)
{if(!m) return true;if(m >= p && dfs(m - p, p, q)) return true;if(m >= q && dfs(m - q, p, q)) return true;return false;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int p, q; cin >> p >> q;int res = 0;for(int i = 1;i <= 1000;i ++){if(!dfs(i, p, q)) res = i;}cout << res << '\n';return 0;
}

然后可以验证几个数，从而得到数学规律 

接下来我们看这道题中使用到的数学方法

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

结论：若a，b均为正整数且互质，那么ax + by，x>=0，y>=0，不能凑出的最大数是
(a - 1)(b - 1) - 1 

#include<iostream>
using namespace std;int n, m;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;cout << (n - 1) * (m - 1) - 1 << '\n';return 0;
}

蚂蚁感冒

1211. 蚂蚁感冒 - AcWing题库

这道题我们会有一个疑问，就是最终所有蚂蚁都会离开杆子吗？
我们可以运用等价的思想来解决，当两只蚂蚁相遇时，正常来说是要调头，我们可以等价为是穿过，所以，最多100秒之后，所有蚂蚁都会穿过。所以，最终所有蚂蚁都会离开杆子。

我们可以分两种情况来讨论：

第一个蚂蚁向右走的情况：
1.右边向左走的，必然被感染
2.右边向右走必然不会被感染
3.左边向左走必然不会被感染
4.左边向右走：
        (1)右边存在向左走，则必然被感染
        (2)右边不存在向左走，则必然不会被感染

第一个蚂蚁向左走的情况：
1.左边向右走的，必然被感染
2.右边向右走的，必然不会被感染
3.左边向左走的，必然不会被感染
4.右边向左走：
        (1)左边存在向右走的，则必然被感染
        (2)左边不存在向右走的，则必然不会被感染 

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 55;int n;
int x[N];int main()
{cin >> n;for (int i = 0; i < n; i ++ ) cin >> x[i];int left = 0, right = 0;    // 分别表示左边向右走的蚂蚁数量，和右边向左走的蚂蚁数量for (int i = 1; i < n; i ++ )if (abs(x[i]) < abs(x[0]) && x[i] > 0) left ++ ; // 当前遍历到的蚂蚁初始在第一只蚂蚁的左边，并且当前蚂蚁向右走else if (abs(x[i]) > abs(x[0]) && x[i] < 0) right ++ ; // 当前遍历到的蚂蚁初始在第一只蚂蚁的右边，并且当前蚂蚁向左走if (x[0] > 0 && right == 0 || x[0] < 0 && left == 0) cout << 1 << endl;else cout << left + right + 1 << endl;return 0;
}

 饮料换购

1216. 饮料换购 - AcWing题库

#include<iostream>
using namespace std;int n, sum;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;sum += n;while(n >= 3){int t = n / 3;int p = n % 3;sum += t;n = t + p;}cout << sum << '\n';return 0;
}

DP

01背包问题

2. 01背包问题 - AcWing题库

#include<iostream>
#include<algorithm>
using namespace std;const int N = 1010;int f[N], v, w, n, m;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1;i <= n;i ++){cin >> v >> w;for(int j = m;j >= 1;j --)if(j >= v) f[j] = max(f[j], f[j - v] + w);}cout << f[m] << endl;return 0;
}

摘花生

1015. 摘花生 - AcWing题库

#include<iostream>
#include<algorithm>
using namespace std;const int N = 110;int T, r, c, g[N][N];int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> T;while(T --){cin >> r >> c;for(int i = 1;i <= r;i ++)for(int j = 1;j <= c;j ++) {cin >> g[i][j];g[i][j] += max(g[i - 1][j], g[i][j - 1]);}cout << g[r][c] << '\n';}return 0;
}

最长上升子序列

895. 最长上升子序列 - AcWing题库

#include<iostream>
#include<algorithm>
using namespace std;const int N = 1010;int n, a[N], f[N];int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1;i <= n;i ++) cin >> a[i];int res = 1;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[i], f[j] + 1);res = max(res, f[i]);}}cout << res << '\n';return 0;
}

地宫取宝

1212. 地宫取宝 - AcWing题库

这道题可以用dfs和DP做，但是dfs会爆时间，我们先看dfs

#include<iostream>
#include<algorithm>
using namespace std;const int N = 55;
const int MOD = 1000000007;int n, m, k, ans, g[N][N];void dfs(int u, int i, int j, int t) // u表示当前拿了几件宝贝, t表示当前价值最大是多少
{// 越界了或u>k了直接返回if(i > n || j > m || u > k) return ;if(i == n && j == m) // 到达终点计算是否合法{if(u == k || u == k - 1 && g[i][j] > t) {ans ++;ans %= MOD;}return ;}// 不选dfs(u, i + 1, j, t);dfs(u, i, j + 1, t);// 选if(g[i][j] > t){dfs(u + 1, i + 1, j, g[i][j]);dfs(u + 1, i, j + 1, g[i][j]);}
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m >> k;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) cin >> g[i][j];dfs(0, 1, 1, -1);cout << ans << '\n';return 0;
}

然后看DP的做法

状态表示需要用到4维数组，刚好与我们dfs中的函数4个参数对应
初始时，我们在左上角，此时需要对数组进行初始化
选取左上角这个位置的宝贝时，    f[1][1][1][w[1][1]] = 1
不选取左上角这个位置的宝贝时，f[1][1][0][-1] = 1
因为C++中坐标没有负数，所以我们对每个宝贝的价值都增加1，这样宝贝的价值就变成了1到13，就可以使用0来表示没有选取任何一个宝贝了

然后看状态计算。
对于当前状态f[i, j, k, c]，可以由前一个状态向下走，也可以由前一个状态向右走，此时就有两个分支了。对于每一个分支，又可以分成是否拿当前这个位置[i, j]的宝贝。对于取的这一个分支，又可以分成前一个最大价值是多少。注意：不取没有什么限制，但是如果要取，则必须满足当前状态的宝物数量不为0，并且当前状态的宝贝最大值等于w[i][j]

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 55, MOD = 1000000007;int n, m, k;
int w[N][N];
int f[N][N][13][14];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 ++ )for (int v = 0; v <= 13; 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 ++ ){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;
}

波动数列

1214. 波动数列 - AcWing题库

设满足题意的一个数列的第一项为x，设di∈{a, -b}，则长度为n的数列为：

由这个数列的和为s，可得：

进一步传化可得：

因为x是整数，所以分子一定是n的倍数，也就是说s 和 (n - 1)d1 + (n - 2)d2 + ... + dn - 1，两者模n的余数是相等的。所以，问题就转化成了有多少种不同的选法，使得
(n - 1)d1 + (n - 2)d2 + ... + dn - 1与s模n的结果相同。这是一个组合问题

我们来看看状态计算的两个状态是怎么推出来的。我们要根据最后一项不同来推，很明显，最后一项不同就是从第i - 1项到第 i 项选+a，还是选-b

假设前i-1项的和为C，则有(以+a为例)：
 移项可得：

所以最后一项是+a的所有方案的状态是f[i - 1, (j - (n - i)a) % n]
       最后一项是+a的所有方案的状态是f[i - 1, (j + (n - i)b) % n]

最终结果就是f[n - 1, s % n]

#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()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int 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 - a * (n - i), n)] + f[i - 1][get_mod(j + b * (n - i), n)]) % MOD;cout << f[n - 1][get_mod(s, n)] << endl;return 0;
}

注意：取模操作需要我们自己实现，因为C++中负数取模是负数，而数列的项中是含有负数项的，所以需要自己实现求正余数