【Noi2011】Noi嘉年华

Source and Judge

Noi2011
bzoj2436

Record

2h

Analysis

请先思考后再展开

题意:
n个值域为2n的区间
分为A、B、C,要求A交B为空
求固定第i个区间或不固定时的最大【A和B中小的集合大小】

那么我们希望求出F[l][r]表示这段值域区间A必选的答案
那么我们考虑枚举前后A选择了多少
然后我们需要f[i][t]表示前缀值前i个A选了t个区间,B最多选多少个
后缀意义下自然也求一个g[i][t],求的话就是枚举两人选的最后一段区间
$f(i,t)=max{f(j,t)+num[j+1][i],f(j,t-num[j+1][i])}$
这样就能求出第一问了,第二问目前是 $O(n^4)$
$cal(l,r,a,b)=min{ f(l-1,a)+f(r+1,b),a+b+num[l][r] }$
$F[l][r]=max{ cal(fl \leq l,r \leq fr,a,b) }$
然后对于每个a,b应该是个二次函数,而且a增b减,用个指针即可

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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
// #define pr pair<int,int>
// #define FR first
// #define SE second
// #define MP make_pair
void chmax(int &x,int y) {x=x>y?x:y;}
const int MAX_N=410;
struct Data{int d,p;}d[MAX_N];
bool cmp(Data a,Data b) {return a.d<b.d;}
int val[MAX_N];
int num[MAX_N][MAX_N],f[MAX_N][MAX_N],g[MAX_N][MAX_N];
int F[MAX_N][MAX_N];
int cal(int l,int r,int a,int b) {return min(f[l-1][a]+g[r+1][b],a+b+num[l][r]);}
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int st,ed;scanf("%d%d",&st,&ed);ed+=st-1;
d[2*i-1]=(Data){st,2*i-1};d[2*i]=(Data){ed,2*i};
}
sort(d+1,d+2*n+1,cmp);
int rx=1;val[d[1].p]=rx;
for(int i=2;i<=n*2;i++)
{
if(d[i-1].d!=d[i].d) rx++;
val[d[i].p]=rx;
}
for(int l=1;l<=rx;l++) for(int r=l;r<=rx;r++)
for(int i=1;i<=n;i++) num[l][r]+=(l<=val[2*i-1] and val[2*i]<=r);
for(int i=1;i<=rx;i++) for(int t=0;t<=n;t++)
for(int j=0;j<i;j++)
{
if(num[1][j]>=t) chmax(f[i][t],f[j][t]+num[j+1][i]);
if(t>=num[j+1][i]) chmax(f[i][t],f[j][t-num[j+1][i]]);
}
for(int i=rx;i>=1;i--) for(int t=0;t<=n;t++)
for(int j=rx+1;j>i;j--)
{
if(num[j][rx]>=t) chmax(g[i][t],g[j][t]+num[i][j-1]);
if(t>=num[i][j-1]) chmax(g[i][t],g[j][t-num[i][j-1]]);
}
int ans=0;for(int i=0;i<=n;i++) chmax(ans,min(f[rx][i],i));
printf("%d\n",ans);
for(int ln=rx;ln>=1;ln--)
for(int l=1;l<=rx-ln+1;l++)
{
int r=l+ln-1,b=num[r+1][rx];
F[l][r]=max(F[l-1][r],F[l][r+1]);
for(int a=0;a<=num[1][l-1];a++)
{
while(b-1>=0 and cal(l,r,a,b-1)>=cal(l,r,a,b)) b--;
chmax(F[l][r],cal(l,r,a,b));
}
}
for(int i=1;i<=n;i++) printf("%d\n",F[ val[2*i-1] ][ val[2*i] ]);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/1d84.html
转载请注明出处,谢谢!