这道题一共有两问,第一问瞎搞 $\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;
}
分类: 文章

Qiuly

井戸の底の空にはまだかすかな希望の光がある……

发表评论

电子邮件地址不会被公开。 必填项已用*标注