P1973 [NOI2011]Noi嘉年华
传送门
题目描述
$NOI2011$ 在吉林大学开始啦！为了迎接来自全国各地最优秀的信息学选手，吉林大学决定举办两场盛大的 $NOI$ 嘉年华活动，分在两个不同的地点举办。每个嘉年华可能包含很多个活动，而每个活动只能在一个嘉年华中举办。
现在嘉年华活动的组织者小安一共收到了$n$个活动的举办申请，其中第 $i$ 个活动的起始时间为 $S_i$，活动的持续时间为$T_i$。这些活动都可以安排到任意一个嘉年华的会场，也可以不安排。
小安通过广泛的调查发现，如果某个时刻，两个嘉年华会场同时有活动在进行（不包括活动的开始瞬间和结束瞬间），那么有的选手就会纠结于到底去哪个会场，从而变得不开心。所以，为了避免这样不开心的事情发生，小安要求不能有两个活动在两个会场同时进行（同一会场内的活动可以任意进行）。
另外，可以想象，如果某一个嘉年华会场的活动太少，那么这个嘉年华的吸引力就会不足，容易导致场面冷清。所以小安希望通过合理的安排，使得活动相对较少的嘉年华的活动数量最大。
此外，有一些活动非常有意义，小安希望能举办，他希望知道，如果第 $i$ 个活动必须举办（可以安排在两场嘉年华中的任何一个），活动相对较少的嘉年华的活动数量的最大值。
输入输出格式
输入格式：
输入的第一行包含一个整数 $n$，表示申请的活动个数。
接下来 $n$ 行描述所有活动，其中第 $i$ 行包含两个整数 $S_i$、$T_i$，表示第 $i$ 个活动从时刻$S_i$开始，持续 $T_i$ 的时间。
输出格式：
输出的第一行包含一个整数，表示在没有任何限制的情况下，活动较少的嘉年华的活动数的最大值。
接下来 $n$ 行每行一个整数，其中第 $i$ 行的整数表示在必须选择第 $i$ 个活动的前提下，活动较少的嘉年华的活动数的最大值。
输入输出样例
输入样例#1：
5
8 2
1 5
5 3
3 2
5 3
输出样例#1：
2
2
1
2
2
2
说明
【样例说明】
在没有任何限制的情况下，最优安排可以在一个嘉年华安排活动$1$, $4$，而在另一个嘉年华安排活动$3$, $5$，活动$2$不安排。
如果输出格式不正确（比如输出不足$n+1$行），得$0$分；
如果输出文件第一行不正确，而且后$n$行至少有一行不正确，得$0$分；
如果输出文件第一行正确，但后$n$行至少有一行不正确，得$4$分；
如果输出文件第一行不正确，但后$n$行均正确，得$6$分；
如果输出文件中的$n+1$行均正确，得$10$分。
分析
首先离散化时间，因为显然与答案与时间的绝对大小没有关系，只取决与相对大小。
思考转移的话，有一堆等着我们转移，显然一个个转移是很不优秀的，那么我们每次一块块转移。
所以，设$tot _ {l,r}$为完全包含在$[l,r]$区间内的活动数。
接下来考虑怎么$DP$。
设$pre _ {i,j}$为在时间$[1,i]$，第一个会场选了$j$个活动，第二个会场最多可以选多少活动（因为要求活动较少的会场的活动数的最大值，那么确定一个，就让另一个最大）。
考虑转移。
显然，转移为：
第一个转移表示将$[l,r]$内的所有活动分到第一个会场，第一个转移表示将$[l,r]$内的所有活动分到第二个会场。
答案就是$max(min(pre _ {cnt,j} , j ))$
其中$cnt$为时间点个数。
但这仅仅只解决了第一个问题。
为了解决第二个问题，我们还要引入后缀$DP$（$pre$为前缀$DP$）$suf _ {i,j}$，$suf _ {i,j}$为在时间$[i,cnt]$，第一个会场选了$j$个活动，第二个会场最多可以选多少活动。
转移和前缀$DP$差不多：
思考第二问。
我们设$[l,r]$内的活动都被一个会场选择了，所以我们才能一块块转移。
但我们不知道在$l$之前和$r$之后选择了多少活动，所以枚举一下。
枚举$l$之前选择了$a$个活动，$r$之后选择了$b$个活动。
我们设$f _ {i,j}$为要求活动较少的会场的活动数的最大值。
那么转移如下：
第一个转移是第一个会场选择的活动数，第二个转移是第二个会场选择的活动数，因为求较小值的最大值，所以先取$min$,再取$max$。
但这里还有一个问题，就是$pre$和$suf$只是局部最优解，不一定是全局最优解。
比如一个活动$[l’,r’]$，其中$l’<l,r’>r$，那么它显然不会被包含进$tot _ {l,r}$，而它即不属于$[1,l]$，又不属于$[r,cnt]$，那么$pre$和$suf$自然也不能包含它，它就废了。
所以这样一定有问题。
那么我们怎么解决它呢？
我们可以枚举转移区间，对于第$i$个活动$[l_i,r_i]$，我们枚举$f _ {l,r} \ ( l < l_i , r > r_i) $，再取最大值就行了。
正确性保证了，但复杂度爆炸了，是$O(n^4)$的。
考虑优化。
发现有单调性（看标签）。
因为在 $pre _ {i,j}$ 中，$j$ 越小，就说明第一个会场在 $[1, i]$ 区间中选择的活动就越少，那么第二个会场就会选择更多。
所以， $j$ 越小， $pre _ {i,j}$ 越大。
即$pre$是一个单调函数，$suf$也一样。
观察式子$min( a+b+tot _ {l,r} , pre _ {i,a}+suf _ {r,b} )$，显然对于一个之前最优决策点$a,b$，我们不可能通过同时增大$a$和$b$获得新的最优解。
所以，我们将$b$从大到小扫一下就行了。
参考资料
wu3412790的洛谷题解
FlashHu的洛谷题解
longlongzhu123的洛谷题解
代码
向大佬们求助：
$min( a+b+tot _ {l,r} , pre _ {l,a}+suf _ {r,b} )$区间端点$l$，$r$重合没事吗？
还有，时间不应该是$s_i+t_i-1$吗？
为什么我这样打就挂了？1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
using namespace std;
template <typename T>inline T read()
{
register T sum=0;
register char cc=getchar();
int sym=1;
while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
if(cc=='-')sym=-1,cc=getchar();
sum=sum*10+cc-'0';
cc=getchar();
while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
return sym*sum;
}
template <typename T>inline T read(T &a)
{
a=read<T>();
return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
a=read(a);
read(b...);
}
int n,cnt,ans,be[maxn],en[maxn],lsh[maxn],tot[maxn<<1][maxn<<1];
int pre[maxn<<1][maxn],suf[maxn<<1][maxn],f[maxn<<1][maxn<<1];
int val(int i,int j,int a,int b)
{
return min(a+b+tot[i][j],pre[i][a]+suf[j][b]);
}
int main()
{
n=read<int>();
for(int i=1;i<=n;i++)
{
be[i]=read<int>();
en[i]=be[i]+read<int>();
lsh[++cnt]=be[i];
lsh[++cnt]=en[i];
}
sort(lsh+1,lsh+1+cnt);
cnt=unique(lsh+1,lsh+1+cnt)-lsh-1;
for(int i=1;i<=n;i++)
{
be[i]=lower_bound(lsh+1,lsh+1+cnt,be[i])-lsh;
en[i]=lower_bound(lsh+1,lsh+1+cnt,en[i])-lsh;
for(int j=1;j<=be[i];j++)
for(int k=en[i];k<=cnt;k++)
tot[j][k]+=1;
}
for(int i=1;i<=cnt;i++)
for(int j=1;j<=n;j++)
pre[i][j]=suf[i][j]=-INF;
for(int i=1;i<=cnt;i++)
for(int j=0;j<=tot[1][i];j++)
for(int k=1;k<=i;k++)
{
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]]);
}
for(int i=cnt;i>=1;i--)
for(int j=0;j<=tot[i][cnt];j++)
for(int k=cnt;k>=i;k--)
{
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]]);
}
for(int i=1;i<=n;i++)ans=max(ans,min(pre[cnt][i],i));
printf("%d\n",ans);
for(int i=1;i<=cnt;i++)
for(int j=i+1;j<=cnt;j++)
for(int a=0,b=n;a<=n;a++)
{
int las=val(i,j,a,b);
while(b&&las<=val(i,j,a,b-1))
las=val(i,j,a,b-1),b-=1;
f[i][j]=max(f[i][j],las);
}
for(int i=1;i<=n;i++)
{
ans=0;
for(int j=1;j<=be[i];j++)
for(int k=en[i];k<=cnt;k++)
ans=max(ans,f[j][k]);
printf("%d\n",ans);
}
return 0;
}