题解：P14332 [JOI2021 预选赛 R2] 活动巡游 / Event Hopping

ljk8886 · 2026-08-10 17:27:28 · 题解

考虑 DP。先按时间 S_i 从小到大排序。令 dp_i 表示强制参加第 i 个活动然后留在城镇 P_i 最多能参加的活动数量。

考虑转移：对于一个活动 i，我们可以枚举上一个参加的活动 j，然后分类讨论上一个参加的活动留在的城镇和现在的城镇的关系：

• 如果 P_i = P_j，那么直接转移：dp_i \leftarrow \max(dp_i, dp_j + 1)，表示直接留在这个城镇不走。

• 如果 P_i \neq P_j，那么就要从 P_j 走到 P_i，花费 D + K \times dp_j。如果想要从 dp_j 转移到 dp_i，需要满足 S_j + D + K \times dp_j + 1 \le S_i，转移方程也是 dp_i \leftarrow \max(dp_i, dp_j + 1)。

但这样是 \mathcal{O}(n ^ 2) 的。

考虑优化。注意到上面所需要满足的条件和 LIS 二分优化的条件很像，那么考虑二分。我们把每种城镇记录下来，不同城镇转移时二分找到最大能满足条件的 dp 值进行转移。相同城镇直接记录最大值即可。

时间复杂度 \mathcal{O}(n \log n)。

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
    ll res = 0, f = 1; char ch = gc();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
    while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
    return res * f;
}
inline void write(ll x)
{
    if (x < 0) x = -x, pc('-');
    if (x > 9) write(x / 10);
    pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 2e5 + 5;
struct node {
    ll p, s;
} a[N];
bool cmp(node x, node y) { return x.s < y.s; }
int n; ll d, k;
ll dp[N];
ll tmp1[N], tmp2[N];
int len1, len2;
int main()
{
    n = read(), d = read(), k = read();
    for (int i = 1; i <= n; i++) a[i].p = read(), a[i].s = read();
    sort(a + 1, a + n + 1, cmp);
//  for (int i = 1; i <= n; i++)
//  {
//      dp[i] = 1;
//      for (int j = 1; j < i; j++)
//      {
//          if (a[i].p == a[j].p && a[j].s + 1 <= a[i].s) dp[i] = max(dp[i], dp[j] + 1);
//          if (a[i].p != a[j].p && a[j].s + d + k * dp[j] + 1 <= a[i].s) dp[i] = max(dp[i], dp[j] + 1);
//      }
//      ans = max(ans, dp[i]);
//  }
    tmp1[++len1] = tmp2[++len2] = 0;
    ll max1 = 0, max2 = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i].p == 1)
        {
            int l = 1, r = len2; ll ans = 0;
            while (l <= r)
            {
                int mid = (l + r) >> 1;
                if (a[tmp2[mid]].s + d + k * dp[tmp2[mid]] + 1 <= a[i].s) l = mid + 1, ans = dp[tmp2[mid]];
                else r = mid - 1;
            }
            dp[i] = max(max1, ans) + 1;
            tmp1[++len1] = i;
            max1 = dp[i];
        }
        else
        {
            int l = 1, r = len1; ll ans = 0;
            while (l <= r)
            {
                int mid = (l + r) >> 1;
                if (a[tmp1[mid]].s + d + k * dp[tmp1[mid]] + 1 <= a[i].s) l = mid + 1, ans = dp[tmp1[mid]];
                else r = mid - 1;
            }
            dp[i] = max(ans, max2) + 1;
            tmp2[++len2] = i;
            max2 = dp[i];
        }
    }
    write(max(max1, max2));
    return 0;
}