init:

首先预处理$tot_{l,r}$表示l,r时间段中的活动有哪些....

然后这个可以用$n^3$的时间预处理

接下来我们再预处理两个数组

$pre_{i,j}$表示1~i时间我们第一个选了x的前提下,第二个选了活动个数的最大值

然后怎么求呢?dp一下

$pre_{i,j}=\max_{k<i}{pre_{k,j}+tot_{i,k},pre_{k,j-tot_{i,k}}}$

你没看错,要么分给第一个会场要么分给第二个,$O(n^3)$

然后我们还能再处理出一个$suf_{i,j}$,就是后缀的选择

很易得出转移方程:

$suf_{i,j}=\max_{k>i}{suf_{k,j}+tot_{j,k},suf_{k,j-tot_{i,k}}}$

这样就做完预处理啦qwq

搞事情:

我们还要计算一个求解的数组$f_{l,r}$表示$[l,r]$区间的活动全部被一边选走,两边最优的最小值

然后我们还有枚举$s_i$之前和$t_i$之后有多少活动给了这一边,所以$x+y+sum_{l,r}$就是第一边选的个数!

而另一边呢?你会发现我们的pre和suf就有用了,可以开眼了!

$pre_{l,x}+suf_{r,y}$就是答案

两部分结合起来,转移方程就是

$f_{l,r}=\max_{x}\max_{y}{x+y+tot_{l,r},pre_{l,x}+suf_{r,y}}$

还没完.....答案并不是$f_{s_i,t_i}$

因为这个pre和suf只是局部最优,仅用他们并不能推出全局最优解,也就是说我们$f_{?,?}$才可能是全局最优解,而我们无法知道这个?

解决方法也很简单$\max_{i<=l}\max_{j>=r}$一定是答案,因为我们虽然每个状态并不一定是全局最优解,但最优解一定在这个数组中

这样我们就可以$O(n^4)$求解f然后TLE了!

用脑袋仔细想想,pre数组随着第二维的增大,他的值只有可能变小,没有说我第一个会场活动多第二个会场跟着变多的道理

也就是说,随着x的增大,y如果随着增大, min前面那个只能越来越大,后面那个越来越小

所以对于x增加我们的y只能从大到小的变换....

然后x一增大y变小挨着找最优决策点就做完了....因为一定min在取到后面那个数之后一定不会再取回之前了.....只会越来越劣

这样决策单调性优化我们就可以$O(n^3)$了...

过hack

但是还有一个问题,由于tot是记录了所有完全包含的,所以会导致如果有两个完全相同的区间,我们tot会钦点他强制都选上,我们的f数组步长为1就会更新出错,而且这个hack在讨论区也给出了

要么更改求f数组的过程,要么使得没有两个相同区间,由于这样其实本质上我们只是缺少了只选择其中几个相同区间的决策,所以我们最后把相同的区间右端点向内扰动一下就好了

code:

#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> v;
int n, m;
struct rec {
	db s, t;
	bool operator<(const rec &x)const {
		return s + t < x.s + x.t;
	}
} a[MAXN];
int pre[MAXN][MAXN], suf[MAXN][MAXN], f[MAXN][MAXN], tot[MAXN][MAXN];
int s[MAXN], t[MAXN]; //强卡区间重复....

inline int getid(db x) {
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

inline void init() {
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	for(int i = 1; i <= n; ++i) {
		s[i] = getid(a[i].s);
		t[i] = getid(a[i].t);
		// printf("activity %d st in : %d ed in :%d \n", i, s[i], t[i]);
	}
	m = v.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], tot[k][i] + pre[k][j]);
				if(j >= tot[k][i]) {
					pre[i][j] = max(pre[i][j], pre[k][j - tot[k][i]]);
				}
			}
			// printf("pre:!%d %d %d?\n", i, j, pre[i][j]);
		}
	}
	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], tot[i][k] + suf[k][j]);
				if(j >= tot[i][k]) {
					suf[i][j] = max(suf[i][j], suf[k][j - tot[i][k]]);
				}
			}
			// printf("suf:!%d %d %d?\n", i, j, suf[i][j]);
		}
	}
	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)]++;
		v.push_back(a[i].s);
		v.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(s[k] >= i && t[k] <= j)
					tot[i][j]++;
			}
			// printf("%d %d %d\n", i, j, tot[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 + tot[i][j], pre[i][x] + suf[j][y]);
				while(y && p0 <= (p1 = min(x + y - 1 + tot[i][j], pre[i][x] + suf[j][y - 1])))
					p0 = p1, --y;
				f[i][j] = max(f[i][j], min(x + y + tot[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?%d?\n", j, pre[m][j]);
	}
	printf("%d\n", ans);
	for(int i = 1; i <= n; ++i) {
		ans = 0;
		for(int j = 1; j <= s[i]; ++j) {
			for(int k = t[i]; k <= m; ++k) {
				ans = max(ans, f[j][k]);
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

七海死了

在弹丸论破扯几把蛋的世界观里她的珍贵才能体现出来吧

但是弹丸论破世界观还是真tm的太扯淡了

绝望篇按理应该很好看的,但是太你妈扯淡了!!!!!