记录第一篇在洛谷的题解诞生

[GCJ 2015 #1A] Mushroom Monster 题解

题意简述

某公司有 $n$ 名员工，每人要在 $0$ 到 $m$ 时刻内进出公司一次，在 $s_{i}$ 离开公司，$t_{i}$ 返回公司，且该公司只有一扇大门，进出时需要保证门处于开启或者能打开的状态，注意在公司内部的员工可以打开门，在外部的员工需要持有钥匙才可以打开。现有 $k$ 把钥匙，问要如何分配，使得门能处于关闭状态的最长总时间是多少？

题目分析

容易发现，公司大门是否要关闭将影响着后一个将进出公司大门的员工，所以将所有员工的离开和返回事件按时间排序后，相邻两个事件之间的时间间隔即可称为一个时间段，每个时间段内的门要么一直开着，要么一直关着。
我们可以通过分析相邻时间间隔上的事件情况来确定公司大门关闭的状态（某些情况下有无钥匙都可以关闭的不分配钥匙直接产生时间贡献，其他情况需要考虑给钥匙还是不给钥匙，此处可以考虑动态规划处理）。

算法设计

$n$ 名员工共有 $2n$ 个事件，设事件序列为 $a_1, a_2, \ldots, a_{2n}$，其中每个事件 $a_i = (time_{i}, id_{i}, flag_{i})$，$time_{i}$ 为事件发生时间，$id_{i}$ 为员工编号，$flag_{i} = 0$ 表示此事件为员工离开公司，$flag_{i} = 1$ 表示此事件为员工返回公司。接着先对事件序列按事件发生时间 $time_{i}$ 进行从小到大排序。

$ans = time_{1} + m - time_{2n}$，其中 $ans$ 为直接贡献的总和。

接下来考虑相邻事件 $a_i$ 和 $a_{i+1}$ 之间的时间段，其长度 $\Delta t = t_{i+1} - t_i$ 是否要关闭。根据 $a_i$ 和 $a_{i+1}$ 的状态，可以分为四种情况：

• 返回 → 离开： 无论钥匙如何分配，该时间段门都可以关闭。直接贡献为 $\Delta t$，直接加到 $ans$ 上。

• 返回 → 返回： 仅当 $a_{i+1}$ 对应的员工有钥匙时，门才可以关闭。贡献可记入该员工 $v_{i+1}$ 中。

• 离开 → 离开： 仅当 $a_i$ 对应的员工有钥匙时，门才可以关闭。贡献可记入该员工 $v_{i}$。

• 离开 → 返回： 此情况较复杂，若为同一员工，相当于该员工短暂离开又返回，只要该员工有钥匙就可以关闭。贡献记入该员工中 $v_{i}$；若为不同员工，则需要两名员工都要有钥匙才能关闭，贡献与两人都相关，这里先计入到 $a_{i+1}$ 对应的员工中，用 $w_{i}$ 记录。

由于双人贡献与相邻时段的事件有关系，我们将所有员工根据事件顺序链接成一个链表。对于员工 $i$，$v_{i}$ 表示仅他本人有钥匙时能贡献的关门时间；$w_{i}$ 表示当他和前一位员工（即链表中的 $nxt_{i}$ ）同时有钥匙时，能额外贡献的关门时间，然后可以使用动态规划求解：设 $dp_{i,j,0/1}$ 表示考虑前 $i$ 个员工，分配了 $j$ 把钥匙，且第 $i$ 个员工没有/有钥匙时的最大关闭时间。从而根据以上4种情况分析容易得到状态转移方程为：

• 第 $i$ 个人不分配钥匙：$dp_{i,j,0} = \max(dp_{i-1,j,0},dp_{i-1,j,1})$
• 第 $i$ 个人分配钥匙：$dp_{i,j,1} = \max(dp_{i-1,j-1,0} + v_{i}, dp_{i-1,j-1,1} + v_{i} + w_{i})$

初始时 $dp_{0,0,0} = ans$。

复杂度分析

排序的时间复杂度为 $O(n \log n)$，动态规划的时间复杂度为 $O(nk)$，可以通过本题。但是由于动态规划的空间复杂度为 $O(n^2)$，可以通过本题，此外还可以用滚动数组，即 $dp_{2,N,2}$ 的设计进行更优化处理。

非常容易理解的代码

#include <bits/stdc++.h>
using namespace std;
const int N = 4005;
int n, m, k, ans, w[N], v[N], nxt[N], dp[2][N][2];

struct node {
	int tim, id, flag;//flag: 0-离开, 1-返回
	bool operator < (const node &b) const {
		return tim < b.tim;
	}
} a[N];

int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[2 * i - 1].tim;
		a[2 * i - 1].id = i, a[2 * i - 1].flag = 0;// 离开
		cin >> a[2 * i].tim;
		a[2 * i].id = i, a[2 * i].flag = 1; //返回
	}
	n *= 2;
	sort(a + 1, a + n + 1);
	ans = a[1].tim + m - a[n].tim;
	for (int i = 1; i < n; i++) {
		int tmp = a[i + 1].tim - a[i].tim;
		if (a[i].flag && !a[i + 1].flag) //返回--离开：可以关闭
			ans += tmp;
		else if (a[i].flag && a[i + 1].flag) //返回--返回：i+1有钥匙则可以关闭
			v[a[i + 1].id] += tmp;
		else if (!a[i].flag && !a[i + 1].flag)//离开--离开：第一个离开的人有钥匙可以关闭
			v[a[i].id] += tmp;
		else if (!a[i].flag && a[i + 1].flag) { //返回--离开：
			if (a[i].id == a[i + 1].id) //同一个人
				v[a[i].id] += tmp;
			else //不同员工：如果两人都有钥匙，可以关闭
				nxt[a[i].id] = a[i + 1].id, w[a[i + 1].id] += tmp;
		}
	}
	//员工时间顺序链
	int head = 0;
	for (int i = 1; i <= n; i++) {
		if (!w[i]) {
			nxt[head] = i;
			while (nxt[head]) {
				head = nxt[head];
			}
		}
	}
	dp[0][0][0] = ans;
	int s = 0;
	for (int i = nxt[0]; i; i = nxt[i]) {
		s ^= 1;
		for (int j = 0; j <= k; j++) {
			dp[s][j][0] = max(dp[s ^ 1][j][0], dp[s ^ 1][j][1]);
			if (j > 0)
				dp[s][j][1] = max(dp[s ^ 1][j - 1][0] + v[i], dp[s ^ 1][j - 1][1] + v[i] + w[i]);
		}
	}
	cout << max(dp[s][k][0], dp[s][k][1]) << endl;
}

声明：本文在 Markdown 排版上使用了生成式 AI 工具进行辅助。

#include <cstdio>
#include <algorithm>
using namespace std;
const int M = 4005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,t,w,ans,b[M],c[M],nxt[M],dp[2][M][M];
struct node
{
	int x,id,fl;
	bool operator < (const node &b) const
	{
		return x<b.x;
	}
}a[2*M];
signed main()
{
	n=read();m=read();k=read();
	for(int i=1;i<=n;i++)
	{
		a[++t]=node{read(),i,0};
		a[++t]=node{read(),i,1};
	}
	sort(a+1,a+1+t);
	ans=a[1].x+m-a[t].x;
	for(int i=1;i<t;i++)
	{
		int w=a[i+1].x-a[i].x;
		if(a[i].fl && !a[i+1].fl) ans+=w;
		if(!a[i].fl && !a[i+1].fl) c[a[i].id]+=w;
		if(a[i].fl && a[i+1].fl) c[a[i+1].id]+=w;
		if(!a[i].fl && a[i+1].fl)
		{
			if(a[i].id==a[i+1].id) c[a[i].id]+=w;
			else nxt[a[i+1].id]=a[i].id,b[a[i].id]+=w;
		}
	}
	int pr=0; 
	for(int i=1;i<=n;i++)
		if(!b[i])
		{
			nxt[pr]=i;
			for(;nxt[pr];pr=nxt[pr]);
		}
	dp[0][0][0]=ans;
	for(int i=nxt[0];i;i=nxt[i])
	{
		w^=1;
		for(int j=0;j<=k;j++)
			for(int t=0;t<=1;t++)
			{
				if(!dp[w^1][j][t]) continue;//illegal states
				dp[w][j][0]=max(dp[w][j][0],dp[w^1][j][t]);
				dp[w][j+1][1]=max(dp[w][j+1][1],dp[w^1][j][t]+t*b[i]+c[i]);
				dp[w^1][j][t]=0;
			}
	}
	printf("%d\n",max(dp[w][k][0],dp[w][k][1]));
}