2436: [Noi2011]Noi嘉年华
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 529 Solved: 382
[Submit][Status][Discuss]
Description
NOI2011 在吉林大学开始啦！为了迎接来自全国各地最优秀的信息学选手，吉林大学决定举办两场盛大的 NOI 嘉年华活动，分在两个不同的地点举办。每个嘉年华可能包含很多个活动，而每个活动只能在一个嘉年华中举办。
现在嘉年华活动的组织者小安一共收到了 n个活动的举办申请，其中第 i 个活动的起始时间为 Si，活动的持续时间为Ti。这些活动都可以安排到任意一个嘉年华的会场，也可以不安排。
小安通过广泛的调查发现，如果某个时刻，两个嘉年华会场同时有活动在进行（不包括活动的开始瞬间和结束瞬间），那么有的选手就会纠结于到底去哪个会场，从而变得不开心。所以，为了避免这样不开心的事情发生，小安要求不能有两个活动在两个会场同时进行（同一会场内的活动可以任意进行）。
另外，可以想象，如果某一个嘉年华会场的活动太少，那么这个嘉年华的吸引力就会不足，容易导致场面冷清。所以小安希望通过合理的安排，使得活动相对较少的嘉年华的活动数量最大。
此外，有一些活动非常有意义，小安希望能举办，他希望知道，如果第i 个活动必须举办（可以安排在两场嘉年华中的任何一个），活动相对较少的嘉年华的活动数量的最大值。
Input
输入的第一行包含一个整数 n，表示申请的活动个数。
接下来 n 行描述所有活动，其中第 i 行包含两个整数 Si、Ti，表示第 i 个活动从时刻Si开始，持续 Ti的时间。
Output
输出的第一行包含一个整数，表示在没有任何限制的情况下，活动较少的嘉年华的活动数的最大值。
接下来 n 行每行一个整数，其中第 i 行的整数表示在必须选择第 i 个活动的前提下，活动较少的嘉年华的活动数的最大值。
Sample Input
8 2
1 5
5 3
3 2
5 3
Sample Output
2
1
2
2
2
HINT
在没有任何限制的情况下，最优安排可以在一个嘉年华安排活动 1, 4，而在另一个嘉年华安排活动 3, 5，活动2不安排。
1≤n≤200 0≤Si≤10^9
1≤Ti≤ 10^9
Source
Solution
一道比较好的DP
首先直接DP是不能得到答案的，所以一步步考虑
先将节目起始时间和终止时间离散化
$num[i][j]$表示从时间$i~j$的节目有多少个，这个特别好求，$O(N^{2})$/$O(N^{3})$都是可以的
$pre[i][j]$表示：截至在时间$i$之前，给一个场地$j$个节目，另一个场地最多有多少节目
$suf[i][j]$表示：截至在时间$i$之后，给一个场地$j$个节目，另一个场地最多有多少节目
$pre[i][j]$,$suf[i][j]$显然是可以DP的，
$pre[i][j]=max(pre[i][j+1],pre[k][j]+num[k][i],pre[k][j-num[k][i])$，$suf[i][j]$求法相同，倒着DP
那么第一问的答案，显然就是$max \left\{ min(pre[end][i],i) \right\} $
那么考虑第二问，要求每个活动必须举办时的情况
那么需要再进行一遍DP，
$dp[i][j]=max(min(x+y+num[i][j],pre[i][x]+suf[j][y])$
直接枚举$x$,$y$进行DP是$O(N^{4})$，显然不行。
但我们发现，x一定时，y是单峰的，当x增大时，y是减少的，所以只需要枚举x即可，y不断减小
这样总的复杂度就是$O(N^3)$
Code
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 500
int N,S[MAXN],T[MAXN],num[MAXN][MAXN],pre[MAXN][MAXN],suf[MAXN][MAXN];
int dp[MAXN][MAXN];
int ls[MAXN<<],tp,top;
void Prework()
{
for (int i=; i<=top; i++)
for (int j=; j<=top; j++)
for (int k=; k<=N; k++)
if (S[k]>=i && T[k]<=j)
num[i][j]++;
for (int i=; i<=top; i++)
for (int j=; j<=N+; j++) pre[i][j]=suf[i][j]=-0x7fffffff;
for (int i=; i<=top; i++)
for (int j=num[][i]; j>=; j--)
{
pre[i][j]=pre[i][j+];
for (int k=; k<=i-; k++)
{
pre[i][j]=max(pre[i][j],pre[k][j]+num[k][i]);
if (j>=num[k][i])
pre[i][j]=max(pre[i][j],pre[k][j-num[k][i]]);
}
}
for (int i=top; i; i--)
for (int j=num[i][top]; j>=; j--)
{
suf[i][j]=suf[i][j+];
for (int k=i+; k<=top+; k++)
{
suf[i][j]=max(suf[i][j],suf[k][j]+num[i][k]);
if (j>=num[i][k])
suf[i][j]=max(suf[i][j],suf[k][j-num[i][k]]);
}
}
}
void DP()
{
for (int i=; i<=top; i++)
for (int j=i+; j<=top; j++)
{
int t=num[j][top],k;
for (k=; k<=num[][i]; k++)
{
while (t)
if (min(k+t+num[i][j],pre[i][k]+suf[j][t])<=min(k+t-+num[i][j],pre[i][k]+suf[j][t-]))
t--;
else break;
dp[i][j]=max(dp[i][j],min(k+t+num[i][j],pre[i][k]+suf[j][t]));
}
}
}
int ans,Ans[MAXN];
int main()
{
N=read();
for (int i=; i<=N; i++)
ls[++tp]=S[i]=read(),ls[++tp]=T[i]=S[i]+read();
stable_sort(ls+,ls+tp+);
top=unique(ls+,ls+tp+)-ls-;
for (int i=; i<=N; i++)
S[i]=lower_bound(ls+,ls+top+,S[i])-ls,T[i]=lower_bound(ls+,ls+top+,T[i])-ls;
Prework();
for (int i=; i<=N; i++)
ans=max(min(pre[top][i],i),ans);
DP();
for (int i=; i<=N; i++)
for (int j=S[i]; j; j--)
for (int k=T[i]; k<=top; k++)
Ans[i]=max(Ans[i],dp[j][k]);
printf("%d\n",ans);
for (int i=; i<=N; i++)
printf("%d\n",Ans[i]);
return ;
}
有点厉害.....