[BZOJ2436][Noi2011]Noi嘉年華（DP）

Address

洛谷 P1973

BZOJ 2436

LOJ #2446

Solution

• NOIP 2018 前的最後一篇博文，為自己的爆零做好準備
• 先把區間端點離散化
• 預處理出：
• c n t [ l ] [ r ] cnt[l][r] cnt[l][r] 表示包含于 [ l , r ] [l,r] [l,r] 的區間個數
• 計算兩個 DP 值
• f [ i ] [ j ] f[i][j] f[i][j] 表示 [ 1 , i ] [1,i] [1,i] 内，第一個數軸放了 j j j 個區間，第二個數軸最多能放多少個區間
• g [ i ] [ j ] g[i][j] g[i][j] 表示 [ i , m ] [i,m] [i,m] 内，第一個數軸放了 j j j 個區間，第二個數軸最多能放多少個區間
• 上面 m m m 表示區間的最右邊界
• 轉移顯然
• f [ i ] [ j ] = max ⁡ k = 0 i − 1 max ⁡ ( f [ k ] [ j − c n t [ k + 1 ] [ i ] ] , f [ k ] [ j ] + c n t [ k + 1 ] [ i ] ) f[i][j]=\max_{k=0}^{i-1}\max(f[k][j-cnt[k+1][i]],f[k][j]+cnt[k+1][i]) f[i][j]=k=0maxi−1​max(f[k][j−cnt[k+1][i]],f[k][j]+cnt[k+1][i])
• g [ i ] [ j ] = max ⁡ k = i + 1 m + 1 max ⁡ ( g [ k ] [ j − c n t [ i ] [ k − 1 ] ] , g [ k ] [ j ] + c n t [ i ] [ k − 1 ] ) g[i][j]=\max_{k=i+1}^{m+1}\max(g[k][j-cnt[i][k-1]],g[k][j]+cnt[i][k-1]) g[i][j]=k=i+1maxm+1​max(g[k][j−cnt[i][k−1]],g[k][j]+cnt[i][k−1])
• 第一問顯然為 max ⁡ min ⁡ ( i , f [ m ] [ i ] ) \max\min(i,f[m][i]) maxmin(i,f[m][i])
• 對于第二問，要強制選擇第 i i i 個區間 [ l i , r i ] [l_i,r_i] [li​,ri​]
• 就相當于選取 l l l 和 r r r 使得 l ≤ l i ≤ r i ≤ r l\le l_i\le r_i\le r l≤li​≤ri​≤r ，強制選擇包含于 [ l , r ] [l,r] [l,r] 的所有的區間
• 然後包含于 [ 1 , l − 1 ] [1,l-1] [1,l−1] 和包含于 [ r + 1 , m ] [r+1,m] [r+1,m] 的區間分别處理
• 于是再定義 h [ l ] [ r ] h[l][r] h[l][r] 表示強制選擇包含于 [ l , r ] [l,r] [l,r] 的區間時，區間個數較少的數軸的區間個數的最大值
• 轉移
• h [ l ] [ r ] = max ⁡ i max ⁡ j min ⁡ ( i + j + c n t [ l ] [ r ] , f [ l − 1 ] [ i ] + g [ r + 1 ] [ j ] ) h[l][r]=\max_i\max_j\min(i+j+cnt[l][r],f[l-1][i]+g[r+1][j]) h[l][r]=imax​jmax​min(i+j+cnt[l][r],f[l−1][i]+g[r+1][j])
• 這是 O ( n 4 ) O(n^4) O(n4) 的，過不去
• 考慮對 f f f 和 g g g 求字尾最大值
• f [ i ] [ j ] f[i][j] f[i][j] 表示 [ 1 , i ] [1,i] [1,i] ，第一個數軸至少選了 j j j 個區間
• g [ i ] [ j ] g[i][j] g[i][j] 表示 [ i , m ] [i,m] [i,m] ，第一個數軸至少選了 j j j 個區間
• 易得 f f f 和 g g g 的第二維單調不增
• 同時對于一個轉移 i i i ， min ⁡ ( i + j + c n t [ l ] [ r ] , f [ l − 1 ] [ i ] + g [ r + 1 ] [ j ] ) \min(i+j+cnt[l][r],f[l-1][i]+g[r+1][j]) min(i+j+cnt[l][r],f[l−1][i]+g[r+1][j]) 是關于 j j j 的上凸函數
• 當 i i i 減少時最優轉移的 j j j 遞增
• 可以用 two pointers 維護 i i i ，和最優的 j j j
• 強制選第 i i i 個區間 [ l i , r i ] [l_i,r_i] [li​,ri​] 的答案為
• max ⁡ j = 1 l i max ⁡ k = r i m h [ j ] [ k ] \max_{j=1}^{l_i}\max_{k=r_i}^mh[j][k] j=1maxli​​k=ri​maxm​h[j][k]
• 複雜度 O ( n 3 ) O(n^3) O(n3)

Code

• 發現常數巨大，果然蒟蒻

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
#define Rof(i, a, b) for (i = a; i >= b; i--)

inline int read()
{
	int res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	return bo ? ~res + 1 : res;
}

template <class T>
inline T Max(const T &a, const T &b) {return a > b ? a : b;}

template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}

const int N = 205, M = N << 1, INF = 0x3f3f3f3f;

int n, l[N], r[N], tm, m, tmp[M], cnt[M][M], f[M][N], g[M][N], le[M], ri[M],
ans, h[M][M];

int main()
{
	int i, j, k;
	n = read();
	For (i, 1, n) l[i] = read(), r[i] = l[i] + read() - 1,
		tmp[++tm] = l[i], tmp[++tm] = r[i];
	std::sort(tmp + 1, tmp + tm + 1);
	m = std::unique(tmp + 1, tmp + tm + 1) - tmp - 1;
	For (i, 1, n)
	{
		l[i] = std::lower_bound(tmp + 1, tmp + m + 1, l[i]) - tmp;
		r[i] = std::lower_bound(tmp + 1, tmp + m + 1, r[i]) - tmp;
	}
	For (i, 0, m + 1) For (j, 0, n) f[i][j] = g[i][j] = -INF;
	For (i, 1, m) For (j, i, m) For (k, 1, n)
		if (i <= l[k] && r[k] <= j) cnt[i][j]++;
	f[0][0] = g[m + 1][0] = 0;
	For (i, 1, m) For (j, 0, n) For (k, 0, i - 1)
	{
		f[i][j] = Max(f[i][j], f[k][Max(0, j - cnt[k + 1][i])]);
		f[i][j] = Max(f[i][j], f[k][j] + cnt[k + 1][i]);
	}
	Rof (i, m, 1) For (j, 0, n) For (k, i + 1, m + 1)
	{
		g[i][j] = Max(g[i][j], g[k][Max(0, j - cnt[i][k - 1])]);
		g[i][j] = Max(g[i][j], g[k][j] + cnt[i][k - 1]);
	}
	For (i, 1, m) For (j, 0, n)
	{
		le[i] = Max(le[i], Min(j, f[i][j]));
		ri[i] = Max(ri[i], Min(j, g[i][j]));
	}
	For (i, 0, n) ans = Max(ans, Min(i, f[m][i]));
	std::cout << ans << std::endl;
	For (i, 0, m + 1) Rof (j, n - 1, 0)
	{
		f[i][j] = Max(f[i][j], f[i][j + 1]);
		g[i][j] = Max(g[i][j], g[i][j + 1]);
	}
	For (i, 1, m) For (j, i, m)
	{
		int p = 0;
		Rof (k, n, 0)
		{
			while (p < n && Min(k + p + cnt[i][j], f[i - 1][k] + g[j + 1][p])
				< Min(k + p + 1 + cnt[i][j], f[i - 1][k] + g[j + 1][p + 1]))
					p++;
			h[i][j] = Max(h[i][j], Min(k + p + cnt[i][j],
				f[i - 1][k] + g[j + 1][p]));
		}
	}
	For (i, 1, n)
	{
		ans = 0;
		For (j, 1, l[i]) For (k, r[i], m)
			ans = Max(ans, h[j][k]);
		printf("%d\n", ans);
	}
	return 0;
}