《P1973 [NOI2011] NOI 嘉年华》

题目描述

NOI2011 在吉林大学开始啦！为了迎接来自全国各地最优秀的信息学选手，吉林大学决定举办两场盛大的 NOI 嘉年华活动，分在两个不同的地点举办。每个嘉年华可能包含很多个活动，而每个活动只能在一个嘉年华中举办。

现在嘉年华活动的组织者小安一共收到了 n 个活动的举办申请，其中第 i 个活动的起始时间为 Si​，活动的持续时间为 Ti​。这些活动都可以安排到任意一个嘉年华的会场，也可以不安排。

小安通过广泛的调查发现，如果某个时刻，两个嘉年华会场同时有活动在进行（不包括活动的开始瞬间和结束瞬间），那么有的选手就会纠结于到底去哪个会场，从而变得不开心。所以，为了避免这样不开心的事情发生，小安要求不能有两个活动在两个会场同时进行（同一会场内的活动可以任意进行）。

另外，可以想象，如果某一个嘉年华会场的活动太少，那么这个嘉年华的吸引力就会不足，容易导致场面冷清。所以小安希望通过合理的安排，使得活动相对较少的嘉年华的活动数量最大。

此外，有一些活动非常有意义，小安希望能举办，他希望知道，如果第 i 个活动必须举办（可以安排在两场嘉年华中的任何一个），活动相对较少的嘉年华的活动数量的最大值。

输入格式

输入的第一行包含一个整数 n，表示申请的活动个数。

接下来 n 行描述所有活动，其中第 i 行包含两个整数 Si​,Ti​，表示第 i 个活动从时刻 Si​ 开始，持续 Ti​ 的时间。

输出格式

输出的第一行包含一个整数，表示在没有任何限制的情况下，活动较少的嘉年华的活动数的最大值。

接下来 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 不安排。

对于 10% 的数据，1≤n≤10。

对于 30% 的数据，1≤n≤40。

对于 100% 的数据，1≤n≤200，0≤Si​≤109，1≤Ti​≤109。

如果输出格式不正确（比如输出不足 n+1 行），得 0 分；

如果输出文件第一行不正确，而且后 n 行至少有一行不正确，得 0 分；

如果输出文件第一行正确，但后 n 行至少有一行不正确，得 4 分；

如果输出文件第一行不正确，但后 n 行均正确，得 6 分；

如果输出文件中的 n+1 行均正确，得 10 分。

代码实现：

#include<bits/stdc++.h> #define db double using namespace std; #define mkp(x,y) (make_pair(x,y)) const int MAXN = 500; map<pair<db, db>, int> mp; vector<db> vec; int n, m; struct nd { db s, t; bool operator<(const nd &x)const { return s + t < x.s + x.t; } } a[MAXN]; int pre[MAXN][MAXN], suf[MAXN][MAXN], f[MAXN][MAXN], cnt[MAXN][MAXN]; int L[MAXN], R[MAXN]; inline int getid(db x) { return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1; } inline void init() { sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); for(int i = 1; i <= n; ++i) { L[i] = getid(a[i].s); R[i] = getid(a[i].t); } m = vec.size(); return; } inline void init2() { for(int i = 1; i <= m; ++i) { for(int j = 1; j <= n; ++j) { pre[i][j] = suf[i][j] = -0x3f3f3f3f; } } for(int i = 1; i <= m; ++i) { for(int j = 0; j <= n; ++j) { for(int k = 1; k < i; ++k) { pre[i][j] = max(pre[i][j], cnt[k][i] + pre[k][j]); if(j >= cnt[k][i]) { pre[i][j] = max(pre[i][j], pre[k][j - cnt[k][i]]); } } } } for(int i = m; i >= 1; ++i) { for(int j = 0; j <= n; ++j) { for(int k = i + 1; k <= m; ++k) { suf[i][j] = max(suf[i][j], cnt[i][k] + suf[k][j]); if(j >= cnt[i][k]) { suf[i][j] = max(suf[i][j], suf[k][j - cnt[i][k]]); } } } } return ; } int main() { scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%lf%lf", &a[i].s, &a[i].t); a[i].t = a[i].s + a[i].t; if(mp.find(mkp(a[i].s, a[i].t)) != mp.end()) a[i].t = a[i].t - mp[mkp(a[i].s, a[i].t)] * 0.001; mp[mkp(a[i].s, a[i].t)]++; vec.push_back(a[i].s); vec.push_back(a[i].t); } init(); for(int i = 1; i <= m; ++i) { for(int j = i + 1; j <= m; ++j) { for(int k = 1; k <= n; ++k) { if(L[k] >= i && R[k] <= j) cnt[i][j]++; } } } init2(); for(int i = 1; i <= m; ++i) { for(int j = i + 1; j <= m; ++j) { int p0, p1; for(int y = n, x = 0; x <= n; ++x) { p0 = min(x + y + cnt[i][j], pre[i][x] + suf[j][y]); while(y && p0 <= (p1 = min(x + y - 1 + cnt[i][j], pre[i][x] + suf[j][y - 1]))) p0 = p1, --y; f[i][j] = max(f[i][j], min(x + y + cnt[i][j], pre[i][x] + suf[j][y])); } } } int ans = 0; for(int j = 1; j <= n; ++j) { ans = max(ans, min(pre[m][j], j)); } printf("%d\n", ans); for(int i = 1; i <= n; ++i) { ans = 0; for(int j = 1; j <= L[i]; ++j) { for(int k = R[i]; k <= m; ++k) { ans = max(ans, f[j][k]); } } printf("%d\n", ans); } return 0; }