$D. $ 给定 $n$ 个 区间 $[l, r]$，一个区间只能被选中一次，在每个点最多选中一个区间，问最多能选多少个区间？
思路：贪心的从左往右选，维护一个当前的时间 $t$，每次先把 $l_i < t$ 的区间加进去集合，之后选集合中 $r_i$ 最小的选中，并把时间 $t$ 更新
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
const int mod = 1e9 + 7;
# define ALL(A) A.begin(),A.end()
void solve() {
int n;
cin >> n;
vector<array<ll,2>> a;
for (int i = 0; i < n; i ++) {
ll l, d;
cin >> l >> d;
ll r = l + d;
a.push_back({l, r});
}
sort(ALL(a));
priority_queue<ll,vector<ll>,greater<ll>> q;
int ans = 0;
int i = 0;
ll t = 0;
while (true) {
if (q.empty()) {
if (i == n)
break;
t = max(t, a[i][0]);
}
while (i < n and a[i][0] <= t) {
q.push(a[i][1]);
i ++;
}
while (q.size() and q.top() < t)
q.pop();
if (q.size()) {
ans += 1;
q.pop();
}
t += 1;
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
T = 1;
// cin >> T;
while (T --)
solve();
return 0;
}
$E.$ 给定图、邻接矩阵 $D$、三个常数 $A, B, C$，节点 $i$ 和 $j$ 之间的边权有两种计算方式：
- 方式一：$D_{i,j} \times A$
- 方式二：$D_{i,j} \times B + C$
求从节点 $1$ 到 节点 $n$，且先用方式一，再用方式二的最短路
思路：只有两种方式，用分层图解决，分为两种状态：
- 状态一：当前在用方式一，后续可以用方式一，也可以用方式二
- 状态二：当前在用方式二，后续只能用方式二
在普通 $Dijkstra$ 的基础上，添加上分层图的状态即可
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
const int mod = 1e9 + 7;
const ll INF = 2e18;
# define ALL(A) A.begin(),A.end()
void solve() {
int n;
ll A, B, C;
cin >> n >> A >> B >> C;
vector<vector<ll>> D(n, vector<ll>(n));
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
cin >> D[i][j];
auto dijkstra = [&](int start) -> vector<array<ll,2>> {
priority_queue<array<ll,3>, vector<array<ll,3>>, greater<array<ll,3>>> q;
vector<array<ll,2>> d(n + 1, {INF, INF});
vector<array<int,2>> vis(n + 1, {false, false});
d[start][0] = 0;
q.push({d[start][0], start, 0});
while (q.size()) {
auto [dist, x, f] = q.top(); q.pop();
if (vis[x][f])
continue;
vis[x][f] = true;
for (int y = 0; y < n; y ++) {
// 火车
ll w = D[x][y] * B + C;
if (d[y][1] > dist + w) {
d[y][1] = dist + w;
q.push({d[y][1], y, 1});
}
// 汽车
if (f == 0) {
w = D[x][y] * A;
if (d[y][0] > dist + w) {
d[y][0] = dist + w;
q.push({d[y][0], y, 0});
}
}
}
}
return d;
};
auto d = dijkstra(0);
cout << ranges::min(d[n - 1]) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
T = 1;
// cin >> T;
while (T --)
solve();
return 0;
}
$F.$ 有两种物品 $A, B$ 供选择，物品有体积、代价、数量三个信息，给 $n$ 个背包，每个背包至少需要 $x$ 体积的物品，问要想满足所有需求，并且每个物品不超过对应的数量，选择物品的总代价最小是多少？
思路：很明显是 01背包，不难想出用二维状态 $dp[i][j]$ 表示用 $i$ 个 $A$ 和 $j$ 个 $B$ 的最小花费，但是如果暴力枚举两个维度会超时，需要优化，可以从最优性考虑，当物品 $A$ 的数量选定时，物品 $B$ 的最小数量一定也是确定的，可以用 $dp[i] = (j, v)$ 表示用 $i$ 个 $A$ 时，$B$ 的最小数量为 $j$，最小花费为 $v$ ，这样每次更新的时候，只需要枚举 $A$ 的数量这一个维度
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
const int mod = 1e9 + 7;
const ll INF = 2e18;
# define ALL(A) A.begin(),A.end()
void solve() {
int n;
cin >> n;
vector<int> d(n, 0);
for (int i = 0; i < n; i ++)
cin >> d[i];
array<ll,2> L, C, K;
for (int i = 0; i < 2; i ++)
cin >> L[i] >> C[i] >> K[i];
vector<array<ll,2>> dp(K[0] + 1, {INF, INF});
dp[0] = {0, 0};
for (auto& x : d) {
vector<array<ll,2>> ndp(K[0] + 1, {INF, INF});
// 枚举这一轮使用的 type 1 的个数
for (int i = 0; i <= K[0]; i ++) {
// type 2 的个数，上取整
int j = (max(0LL, x - L[0] * i) + L[1] - 1) / L[1];
if (j > K[1])
continue;
// 上一轮的 type 1
for (int k = 0; i + k <= K[0]; k ++) {
auto& [l, v] = dp[k];
if (l + j <= K[1]) {
ll w = v + i * C[0] + j * C[1];
if (w < ndp[i + k][1])
ndp[i + k] = {l + j, w};
}
}
}
dp = ndp;
}
ll ans = INF;
for (int i = 0; i <= K[0]; i ++)
ans = min(ans, dp[i][1]);
if (ans == INF)
ans = -1;
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
T = 1;
// cin >> T;
while (T --)
solve();
return 0;
}
$G.$ 给定一个字符串 $s$ 和一个常数 $p$，每次可以移除 $s$ 中的 $of$ 以及之后的至多 $p$ 个字符，问移除后，$s$ 的最小长度是多少？
思路：区间 DP，用 $dp[l][r]$ 表示 $s[l:r]$ 移除后的最小长度， 每增加一个字符，在不移除的情况下， $dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + 1$，如果可以移除的话，我们不妨只考虑 $s[l] = o$ 的区间 （基于最优性，这样的区间移除后，长度是最小的，取最小值的情况下，一定会被取到），在区间 $[l, r]$ 内找到满足 $s[k] = f$ 的位置 $k$，如果 $[l + 1, k - 1]$ 这一段可以被移除，即 $dp[l + 1][k - 1] = 0$，说明可以移除 $s[l]$ 和 $s[k]$，就移除，并且移除后续的 $p$ 个字符，保证移除后的长度最小，更新 $dp[l][r] = min(dp[l][r], max(0, dp[k + 1][r] - p))$
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
const int mod = 1e9 + 7;
const ll INF = 2e18;
# define ALL(A) A.begin(),A.end()
void solve() {
string s;
int p;
cin >> s >> p;
int n = s.size();
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
for (int len = 1; len <= n; len ++)
for (int l = 1; l + len - 1 <= n; l ++) {
int r = l + len - 1;
if (l == r) {
dp[l][r] = 1;
continue;
}
dp[l][r] = 1 + min(dp[l][r - 1], dp[l + 1][r]);
if (s[l - 1] == 'o') {
// f 所在的位置
for (int k = l; k <= r; k ++) {
if (s[k - 1] == 'f' and dp[l + 1][k - 1] == 0) {
dp[l][r] = min(dp[l][r], max(dp[k + 1][r] - p, 0));
}
}
}
}
cout << dp[1][n] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
T = 1;
// cin >> T;
while (T --)
solve();
return 0;
}
