G. 收集
由于稀有度相同的物品需要一起处理,我们先把他们聚集到一起。
类似这样:
vector<int> g[maxn];
...
{
cin >> x >> c;
g[c].push_back(x);
}
那么我们需要一个贪心的思路:
- 肯定是按 ccc 从小往大收集的;
- 对于相同的 ccc 收集完最后一个肯定是要么停留最左边要么停留在最右边。
故设 dp(i,0)dp(i,0)dp(i,0) 表示收集完稀有度为 iii 的物品后停留在最左边,dp(i,1)dp(i,1)dp(i,1) 则表示停留在最右边。
对于转移,则是讨论一下:
- 收集完第 i−1i-1i−1 层的物品后,在最左边还是最右边,将来要停留在这一层的最左边还是最右边,即 dp(i−1,0/1)dp(i-1,0/1)dp(i−1,0/1) 转移到 dp(i,0/1)dp(i,0/1)dp(i,0/1)。
注意的是,可能存在某一层是没有物品的,而下一层是有物品的,需要存储上一层的 c,设其为 pre。则状态转移使用 dp[pre][]dp[pre][]dp[pre][] 而不是 dp[i−1][]dp[i-1][]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. 选择
对于每一个 iii,我们考虑让 aia_iai 和 bib_ibi 之间建一条边,则这些边之间形成了若干个环
则原问题等价于对于每个环,任意两条相邻的边至少选一条,不同的环之间没有限制
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;
}