【题解】[CTSC2000]快乐的蜜月

· · 题解

第一道 CTSC！发篇题解纪念一下。

首先，题目输入非常花里胡哨，我们可以将输入的日期变成区间，什么 t 都变成区间权值，这样我们可以得到简化版题意：

给定一些区间，每个区间有一个权值，选出一些不相交区间，求权值和第 k 大的和。

（为下文讲述方便，我们规定所有的区间均为左开右闭，）

考虑如何解决第 k 大，这里有一道不能说相似，只能说相同的题：P1858 多人背包，我们考虑类似的 DP：令 f_{i,j} 意为前 j 天收入第 i 大是多少。注意这里我们只考虑完整的区间，否则极其难以实现。

考虑转移，显然 f_{i,j} 可以从 f_{x,j-1} 转移得到，还有就是如果存在以 j 结尾的区间 [l,j)，可以从 f_{x,l}+\text{这个区间的权值} 转移得到。可以从得到递推式：

其中 \max_i 意为第 i 大。特别注意：第 k 大不是从第 k 大转移而来，而是所有备选转移中第 k 大的。

如果直接 DP，并使用 nth_element 求解第 k 大，复杂度 \mathcal{O}(k^2(d+r))，d 代表天数，需要优化。

观察发现对于 f_{i,j}，j 相同意为着备选转移相同，考虑如何实现前 k 大从而同时转移 i 相同的 f_{i,j}，注意到操作是对若干个有序区间求第 k 大，考虑归并。维护一个队列 Q 表示当前的前 k 项。每次加入一个新序列，维护两个序列的头指针，将更大的放入队列中。这样可以做到线性求前 k 大。

通过代码的精细实现，我们可以做到 \mathcal{O}(k^2d+kr) 的复杂度，足以通过此题。注意相同的数算作相同的排名。

具体细节见代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;
constexpr int max_d = 366, max_n = 20000, max_t = 100, max_k = 100;
const int mth[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365}, NINF = 0xcfcfcfcf;

vector<int> prv[max_d+1];
queue<int> q[2];
int l[max_n], val[max_n], ty[max_t], f[max_k][max_d+1];
bool isby;
// 月、日转日期
int dt(int m, int d) { return mth[m-1] + d + ((m > 2)? isby:0); }

int main()
{
    memset(f, 0xcf, sizeof f); // -INF

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int k, t, n, y;

    cin >> k >> t >> y >> n;
    isby = (!(y % 4) && (y % 100)) || !(y % 400); // 判闰年

    char sep;
    for (int i = 0, ta, tb, tr; i < n; i++)
    {
        cin >> ta >> sep >> tb, l[i] = dt(ta, tb);
        cin.ignore(3, EOF);
        cin >> ta >> sep >> tb >> val[i], tr = dt(ta, tb); // 输入处理

        prv[tr].push_back(i);
    }
    for (int i = 0; i < t; i++)
        cin >> ty[i];

    for (int i = 0; i < n; i++)
        val[i] = ty[val[i]-1];
    for (int i = 1; i <= max_d; i++)
        for (auto x : prv[i])
            val[x] *= i - l[x]; // 将类别变成权值

    f[0][0] = 0;
    queue<int> *qp = q, *qn = q + 1;
    for (int i = 1, tp, lstp; i <= max_d; i++)
    {
        for (int j = 0; j < k; j++) // f[i,j] <- f[x,j-1]
        {
            if (f[j][i-1] < 0)
                break;
            qp->push(f[j][i-1]);
        }
        for (auto x : prv[i])
        {
            tp = 0; // 开始归并
            while (!qp->empty() && tp < k && f[tp][l[x]] >= 0 && qn->size() < k)
            {
                if (qp->front() > f[tp][l[x]] + val[x])
                    qn->push(lstp = qp->front()), qp->pop();
                else
                    qn->push(lstp = f[tp++][l[x]] + val[x]);
                // 把重复的删掉
                while (!qp->empty() && qp->front() == lstp)
                    qp->pop();
                while (tp < k && f[tp][l[x]] + val[x] == lstp)
                    tp++;
            }

            while (!qp->empty() && qn->size() < k)
                qn->push(lstp = qp->front()), qp->pop();
            while (tp < k && f[tp][l[x]] >= 0 && qn->size() < k)
                qn->push(lstp = f[tp++][l[x]] + val[x]);

            while (!qp->empty())
                qp->pop();
            swap(qp, qn); // 滚动队列（雾
        }

        for (int j = 0; j < k && !qp->empty(); j++)
        {
            f[j][i] = qp->front();
            qp->pop();
        }
        while (!qp->empty()) // 清空队列
            qp->pop();
        while (!qn->empty())
            qn->pop();
    }
     // 特判 -1
    cout << ((f[k-1][max_d-1] != NINF)? f[k-1][max_d-1]:-1) << endl;

    return 0;
}