ch03 部分题目思路

G. 收集

由于稀有度相同的物品需要一起处理，我们先把他们聚集到一起。
类似这样：

vector<int> g[maxn];
...
{
  cin >> x >> c;
  g[c].push_back(x);
}

那么我们需要一个贪心的思路：

• 肯定是按 $c$ 从小往大收集的；
• 对于相同的 $c$ 收集完最后一个肯定是要么停留最左边要么停留在最右边。

故设 $dp(i,0)$ 表示收集完稀有度为 $i$ 的物品后停留在最左边，$dp(i,1)$ 则表示停留在最右边。

对于转移，则是讨论一下：

• 收集完第 $i-1$ 层的物品后，在最左边还是最右边，将来要停留在这一层的最左边还是最右边，即 $dp(i-1,0/1)$ 转移到 $dp(i,0/1)$。

注意的是，可能存在某一层是没有物品的，而下一层是有物品的，需要存储上一层的 c，设其为 pre。则状态转移使用 $dp[pre][]$ 而不是 $dp[i-1][]$

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll a[200010][2], x;
ll dp[200010][2]; // dp[i][0]: 从小到大走；dp[i][1]：从大往小走
bool vis[200010];
int main() {
    int n, c;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        a[i][0] = INT_MAX; // c == i 的位置最小值
        a[i][1] = INT_MIN; // c == i 的位置最大值
    }
    for (int i = 1; i <= n; ++i) {
        cin >> x >> c;
        a[c][0] = min(a[c][0], x);
        a[c][1] = max(a[c][1], x);
        vis[c] = 1;
    }
    int p = 0; // 前一个 c
    vis[n + 1] = 1; // 最后一层回到位置 0, a[n+1][0] = a[n+1][1] = 0
    for (int i = 1; i <= n + 1; ++i) {
        if (!vis[i]) continue;
        for (int j = 0; j < 2; ++j) {
            dp[i][j] = min(abs(a[p][0] - a[i][j]) + dp[p][1], 
                abs(a[p][1] - a[i][j]) + dp[p][0]) + a[i][1] - a[i][0]; 
        }
        p = i;
    }
    cout << dp[n + 1][0] << endl;
    return 0;
}

H. 选择

对于每一个 $i$，我们考虑让 $a_i$ 和 $b_i$ 之间建一条边，则这些边之间形成了若干个环
则原问题等价于对于每个环，任意两条相邻的边至少选一条，不同的环之间没有限制
dp 算出每个环选点的方案数，然后再乘起来，就是总的方案数

• 相信大家都会做一排物品，相邻两件至少选一件，求方案数记作 f[i]

• 现在处理环记作 g[i]，将下面两个方案相加

  • 最后一个不选：f[i-3]
  • 最后一个选：f[i-1]

可以先递推计算 f，再递推计算 'g'

也可以整理得到： g[i] = f[i-3] + f[i-1] = (f[i-4]+f[i-5]) + (f[i-2]+f[i-3]) = (f[i-2]+f[i-4]) + (f[i-3]+f[i-5]) = g[i-1] + g[i-2]

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll M = 998244353;
const int maxn = 2e5 + 10;

// 相邻的数至少选一个
// 线性：f[i] = f[i-2] + f[i-1]
// 环形：g[i] = f[i-3] + f[i-1] --> g[i] = g[i-1] + g[i-2]
ll g[maxn];
int a[maxn], bi, nxt[maxn];
bool vis[maxn];
int main() {
    g[1] = 1, g[2] = 3;
    for (int i = 3; i < maxn; ++i) {
        g[i] = (g[i - 1] + g[i - 2]) % M;
    }

    int n, x, b;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        cin >> bi;
        nxt[a[i]] = bi;
    }
    ll res = 1;
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            int p = i, cnt = 0;
            while (!vis[p]) {
                vis[p] = 1, ++cnt;
                p = nxt[p];
            }
            res = res * g[cnt] % M;
        }
    }
    cout << res << endl;
    return 0;
}