Terminus

小国王 1064. 小国王 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include <cstring>#include <iostream>#include <vector>using namespace std;typedef long long LL;const int N = 12, M = 1 << 10, K = 110;int n, m;// state 记录所有合法状态vector<int> state;// cnt[i] 记录状态 i 中包含多少个 1int cnt[M];// head[i] 记录所有可以转移到状态 i 的状态vector<int> head[M];// DP 数组LL f[N][K][M];// 检查一个状态是不是合法状态boo ...

1049. 大盗阿福 这道题其实就是 LeetCode 打家劫舍。可以用状态机的方式来思考。 1234567891011121314151617181920212223#include <iostream>using namespace std;const int N = 1e5 + 10, INF = 0x3f3f3f3f;int f[N][2];int w[N];int main() { int T; cin >> T; while (T--) { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> w[i]; f[0][0] = 0, f[0][1] = -INF; for (int i = 1; i <= n; i++) { f[i][0] = max(f[i - 1][0], f[i - 1][1]); f[i][1] = f[i - 1][0] + w[i];  ...

2006. 差的绝对值为 K 的数对数目 12345678910111213141516const int N = 110;int h[N];class Solution { public: int countKDifference(vector<int>& nums, int k) { memset(h, 0, sizeof h); int cnt = 0; for (int i = 0; i < nums.size(); i++) { int t = nums[i]; if (t - k >= 0) cnt += h[t - k]; if (t + k <= 100) cnt += h[t + k]; h[t]++; } return cnt; }};

1021. 货币系统 完全背包问题求方案数。 12345678910111213141516171819202122#include <iostream>using namespace std;typedef long long LL;const int N = 3010;int n, m;LL f[N];int main() { cin >> n >> m; f[0] = 1; for (int i = 0; i < n; i++) { int v; cin >> v; for (int j = v; j <= m; j++) { f[j] += f[j - v]; } } cout << f[m] << endl; return 0;} 532. 货币系统 求极大线性无关组中的向量个数。完全背包问题。 a1,a2,… ,ana_1, a_2, \dotso, a_na1​,a2​,…,an​ ...

1020. 潜水员 多维费用 01 背包。 背包问题中，根据题目的问题来定义状态表示和进行状态初始化。 问题 状态定义 求最大值 花费不超过 求方案数 花费恰好为 求最小值 花费至少为 如果题目问最大值，对于不合法状态就设置成负无穷，在取 max 的时候会被丢弃； 如果题目问最小值，对于不合法状态就设置成正无穷，在取 min 的时候会被丢弃； 如果题目问方案数，对于不合法状态就设置成 0，在累加时不会有任何方案数贡献； 这道题 f(i,j,k)f(i, j, k)f(i,j,k) 表示：所有从前 i 个物品中选，氧气量至少为 j，氮气量至少为 k 的选法的气缸重量最小值。 初始条件 f(0,0,0)=0f(0, 0, 0) = 0f(0,0,0)=0，从含义出发：从前 0 个物品中选（说明一个也不选），氧气量至少为 0，氮气量至少为 0 的选法的气缸重量最小值，显然是 0。 其他 f(0,j,k)f(0, j, k)f(0,j,k) 不合法，从含义出发：从前 0 个物品中选（说明一个也不选），氧气量至少为 j，氮气量至少为 k 的选法的气缸重量最小值，显 ...

8. 二维费用的背包问题 01 背包，二维费用 123456789101112131415161718192021#include <iostream>using namespace std;int n, v, m;const int N = 110;int f[N][N];int main() { cin >> n >> v >> m; for (int i = 0; i < n; i++) { int vi, mi, wi; cin >> vi >> mi >> wi; for (int j = v; j >= vi; j--) { for (int k = m; k >= mi; k--) { f[j][k] = max(f[j][k], f[j - vi][k - mi] + wi); } } } cout << f[v][m] ...

当空间优化成一维之后，只有完全背包问题的体积是从小到大循环的。 枚举顺序： 123for 物品 for 体积 for 决策 423. 采药 01 背包问题 总限制时间是背包体积，每棵草药相当于物品，草药价值是物品价值，采集草药花费的时间是物品所占空间。 123456789101112131415161718#include <iostream>using namespace std;const int N = 1010;int f[N], w[N], v[N];int n, m;int main() { cin >> n >> m; for (int i = 1; i <= m; i++) cin >> v[i] >> w[i]; for (int i = 1; i <= m; i++) { for (int j = n; j >= v[i]; j--) { f[j] = max(f[j], f[j - v[i]] + w[i]); } ...

1010. 拦截导弹 对偶问题： 对于一个序列，求： 最长上升子序列 最少用多少个费上升子序列可以覆盖整个序列 答案是一样的。 Dilworth 定理 Dilworth Wikipedia 12345678910111213141516171819202122232425262728293031#include <iostream>using namespace std;const int N = 1010;int f[N], g[N], a[N];int n;int main() { while (cin >> a[n]) n++; int res = 0; for (int i = 0; i < n; i++) { f[i] = 1; for (int j = 0; j < i; j++) { if (a[j] >= a[i]) { f[i] = max(f[i], f[j] + 1); } } res = ma ...

895. 最长上升子序列 123456789101112131415161718192021222324#include <iostream>using namespace std;const int N = 1010;int f[N];int a[N];int n;int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { f[i] = 1; for (int k = 1; k < i; k++) { if (a[k] < a[i]) { f[i] = max(f[i], f[k] + 1); } } } int ans = -1; for (int i = 1; i <= n; i++) ans = max(ans, f[i]); cout <&l ...

fcf6d42fef418147bcf48ca76b66125152e2336fed8b0d4a53d1983b66f08940d00548fefbc1e9673138df3ea7dbd0ab347d7eac9c1e1e6e10cb36065033085a28e90af881cb462429cf7d4439108527f29b0f5cebdd46090f75b0f989e19f576bfc8c81509b211376729892de073d5c6dde136e6145b6b9f02fa08a4cb7a295e2fd5d97f2f3755eec3189a87906a62ba701463f2743f432faaa1f7d8212a7936dbc8454525dc157a7d5e983e7f709836f9a3f489033fed096ee5dae6ced2f87e7f107f2cf1eebbd79c0ab50fcbad5a2598f42124f0bd48857c6dc02de2e2a7708cddd1effecfaeb8e9efaf72fc3d5837ef78429fda9bd6ab ...