这道题一共有两问，第一问瞎搞 $\texttt{DP}$ ，第二问如果直接 $\texttt{DP}$ 的话复杂度是 $O(n^4)$ 的过不去，这个时候需要用到决策单调性优化复杂度就可以降低至 $O(n^3)$ ，这样就过了。我们先来讨论一下第一问的做法。
时间的范围太大了，我们需要离散化一下。离散化后时间就控制在 $0$ 到 $2n$ 的范围内了。
首先可以发现最终的答案一定就是一段一段时间，每一段时间内的活动都是在同一个会场举行。我们可以预处理一个 $tot_{l,r}$ 表示完全在时间 $l,r$ 之内的活动有多少个。计算直接暴力，预处理的复杂度为 $O(n^3)$ 。
然后设一个 $pre_{i,j}$ 表示 $1$ 到 $i$ 的时间一个会场的活动数为 $j$ 时另一个会场的最大活动数。那么转移的话我们枚举一个时间 $k$ ，然后考虑 $k$ 到 $i$ 这段时间中的所有活动分配给哪个会场即可。可以得到转移方程：
$$pre_{i,j}=\max\limits_{k=1}^{i}{pre_{k,j}+tot_{k,i},pre_{k,j-tot_{k,i}}}$$
这里我们 $pre$ 方程的定义中” 一个会场” 就是一号会场，” 另一个会场” 就是二号会场 $。pre_{k,j}+tot_{k,i}$ 就是将 $k$ 到 $i$ 这段时间中所有活动都分配给了二号会场，$pre_{k,j-tot_{k,i}}$ 很显然就是分配给了一号会场。计算时枚举 $i,j,k$ ，复杂度是 $O(n^3)$ 。(其实准确的复杂度带个常数，因为 $i$ 枚举的是时间，而时间最大是 $2n$ 的) 。
我们设离散化后时间总长为 $m$ ，那么答案显然为 $\max\limits_{i=1}^m{\min(pre_{m,i},i)}$ 。接下来我们解决第二问。
我们的 $tot_{l,r}$ 统计的就是完全在时间 $l,r$ 的区间有多少个。那么对于第 $i$ 个活动，设该活动的起始时间与终止时间分别为 $s_i,t_i$ ，那么我们再考虑一对 $x,y \ \ (x\leq s_i,t_i\leq y)$ ，那么如果我们将答案计算上 $tot_{x,y}$ ，那么也就选择了第 $i$ 个活动了。
我们设 $f_{i,j}$ 表示一号会场强制选择 $i$ 到 $j$ 时间中的所有活动时的最优答案。(注意这里的最优答案就是两个会场中活动少的一方的最大值，我们只是考虑在一号会场强制选择 $i$ 到 $j$ 中的所有活动的情况下考虑最优的全局答案) 。
继续看向一号会场，假设在 $i$ 前面的时间中一号会场已经合法举办了 $x$ 场活动，在 $j$ 后面的时间中也合法举办了 $y$ 场活动。那么我们枚举 $i,j,x,y$ 也可以得到二号会场的活动数：$i$ 前面的时间种有 $pre_{i,x}$ 场活动，$j$ 后面的时间中有…… 诶这里用 $pre$ 貌似不是很好表示诶，于是我们新定义一个 $suf$ ，$suf_{i,j}$ 表示 $i$ 到 $m$ 的时间一个会场的活动数为 $j$ 时另一个会场的最大活动数，$suf$ 的状态转移方程和 $pre$ 的同理。
枚举 $i,j,x,y$ 后就可以得到两个会场的活动个数，那么就可以直接算答案了：
$$f_{i,j}=\max\limits_{x=1}^{m}\max\limits_{y=1}^{m}{\min(x+tot_{i,j}+y,pre_{i,x}+suf_{j,y})}$$
但是这样子的复杂度是 $O(n^4)$ 的，过不了。
不过，我们会发现，对于单调递增的 $x$ ，对应的最优的 $y$ 一定是单调递减的 。为什么呢？首先对于一个单调递增的 $i$ ，$pre_{x_i},suf_{x_i}$ 一定是单调递减的 ( $x$ 为任意数) 。那么如果对于单调递增的 $x$ ，$pre_{i,x}$ 一定是单调递减的，这个时候如果 $y$ 单调递增也就意味着 $suf_{j,y}$ 会单调递减，那么 $x+tot_{i,j}+y$ 和 $pre_{i,x}+suf_{j,y}$ 将会越拉越大，对于答案显然是不利的。反过来，如果 $y$ 是单调递减的，那么就会相对比较均衡。(感性理解理解……)
那么我们就不需要枚举 $y$ 了，只需要扫一扫就好了，最终计算 $f$ 的时间复杂度为 $O(n^3)$ 。
最终统计答案的时候，对于一个活动 $i$ ，我们的答案显然为 $\max\limits_{x=1}^{s_i}\max\limits_{y=t_i}^{m}f_{x,y}$ 。必须满足 $x\leq s_i,t_i\leq y$ ，因为这样就会满足一定会选择第 $i$ 个活动。
Code:
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define F(i,j,k) for((i)=(j);(i)<=(k);++i)
#define R(i,j,k) for((i)=(j);(i)>=(k);--i)
const int N=4e2+9;
const int inf=1e9+9;
int n,m,i,j,k,l,r,s[N],t[N],b[N];
int tot[N][N],pre[N][N],suf[N][N],f[N][N];
inline int IN() {
char ch;bool flag=0;int x=0;
while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(flag) x=-x;return x;
}
inline int calc(int x,int y)
{return min(x+tot[l][r]+y,pre[l][x]+suf[r][y]);}
int main() {
n=IN();
F(i,1,n) b[++m]=s[i]=IN(),b[++m]=t[i]=IN()+s[i];
sort(b+1,b+1+m),
m=unique(b+1,b+1+m)-b-1;/*离散化去重*/
F(i,1,n) {
s[i]=lower_bound(b+1,b+1+m,s[i])-b;
t[i]=lower_bound(b+1,b+1+m,t[i])-b;
F(l,1,s[i]) R(r,m,t[i]) ++tot[l][r];/*计算出 tot*/
}
F(i,1,m) F(j,1,n) pre[i][j]=suf[i][j]=-inf;/*初始化*/
/*----------计算出 pre 和 suf----------*/
F(i,1,m) F(j,0,tot[1][i]) F(k,1,i) {
pre[i][j]=max(pre[i][j],pre[k][j]+tot[k][i]);
if(j>=tot[k][i]) pre[i][j]=max(pre[i][j],pre[k][j-tot[k][i]]);
}
R(i,m,1) F(j,0,tot[i][m]) F(k,i,m) {
suf[i][j]=max(suf[i][j],suf[k][j]+tot[i][k]);
if(j>=tot[i][k]) suf[i][j]=max(suf[i][j],suf[k][j-tot[i][k]]);
}
/*计算 f*/
F(l,1,m) F(r,l+1,m) for(int y=n,x=0;x<=n;++x) {/*y 当做指针扫一遍*/
int old_calc=calc(x,y),new_calc;
while(y&&old_calc<=(new_calc=calc(x,y-1))) --y,old_calc=new_calc;
f[l][r]=max(f[l][r],calc(x,y));/*转移*/
}
/*输出答案*/
int ans=0;
F(i,1,n) ans=max(ans,min(pre[m][i],i));
printf("%d\n",ans);/*第一问*/
F(i,1,n) {
ans=0;
F(l,1,s[i]) R(r,m,t[i]) ans=max(ans,f[l][r]);
printf("%d\n",ans);/*第二问*/
}return 0;
}
0 条评论