自动搬运

查看原文

来自洛谷，原作者为

	5ab_juruo May you find some comfort here

搬运于2025-08-24 22:02:09，当前版本为作者最后更新于2021-08-07 23:46:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

第一道 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{这个区间的权值}$ 转移得到。可以从得到递推式：

$$f_{i,j}=\begin{cases}\max_i({}_{x=1}^{k}f_{x,j-1},{}_{x=1}^{k}f_{x,l})&\text{存在区间}[l,j)\\\max_i({}_{x=1}^{k}f_{x,j-1})&\text{otherwise}\end{cases} $$

其中 $\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;
}