题目链接

题解

看这\(O(n^3)\)的数据范围，可以想到区间\(dp\)

发现同一个会场的活动可以重叠，所以暴力求出\(num[l][r]\)表示离散化后\([l,r]\)的完整活动数

我们的目标求出\(F[l][r]\)表示\([l,r]\)必须选时，二者的最小值

我们不妨令\(A\)选了\([l,r]\)，我们枚举\(A\)在\([1,l - 1]\)和\([r + 1,tot]\)各选了多少，求出此时\(B\)能选的最大值

如果我们能求出\(f[i][j]\)表示\([1,i]\)中\(A\)选了\(j\)个时\(B\)能选的最大值，\(g[i][j]\)同理表示后缀，就可以求出\(F[l][r]\)

\(f[i][j]\)可以枚举断点\(k\)从而\(O(n^3)\)转移

\[f[i][j] = max\{f[k][j] + num[k + 1][i],f[i][j - num[k + 1][i]]\}
\]

\(F[l][r]\)的转移是\(O(n^4)\)，这个过程中我们\(O(n^2)\)枚举了\(A\)在两端的选取个数

感性理解一下，当\(A\)在左端选多时，为了使答案更优，右端应该选少一些，所以左端增大的同时右端应该是单调变化的

用一个指针维护右端即可\(O(n^3)\)

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<vector>

#include<queue>

#include<cmath>

#include<map>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u]; k; k = ed[k].nxt)

#define cls(s,v) memset(s,v,sizeof(s))

#define mp(a,b) make_pair<int,int>(a,b)

#define cp pair<int,int>

using namespace std;

const int maxn = 405,maxm = 100005,INF = 100000000;

const double eps = 1e-9;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}

	return flag ? out : -out;

}

int n,L[maxn],R[maxn],b[maxn],bi,tot;

int f[maxn][maxn],g[maxn][maxn],num[maxn][maxn];

int F[maxn][maxn];

inline int getn(int x){return lower_bound(b + 1,b + 1 + tot,x) - b;}

inline int cal(int l,int r,int x,int y){

	return min(x + y + num[l][r],f[l - 1][x] + g[r + 1][y]);

}

void work(){

	for (int j = 1; j <= n; j++) f[0][j] = -INF;

	for (int i = 1; i <= tot; i++)

		for (int j = 0; j <= n; j++){

			f[i][j] = -INF;

			for (int k = 0; k < i; k++){

				int tmp = -INF;

				if (num[1][k] >= j) tmp = max(tmp,f[k][j] + num[k + 1][i]);

				if (num[k + 1][i] <= j) tmp = max(tmp,f[k][j - num[k + 1][i]]);

				f[i][j] = max(f[i][j],tmp);

			}

		}

	for (int j = 1; j <= n; j++) g[tot + 1][j] = -INF;

	for (int i = tot; i; i--)

		for (int j = 0; j <= n; j++){

			g[i][j] = -INF;

			for (int k = tot + 1; k > i; k--){

				int tmp = -INF;

				if (num[k][tot] >= j) tmp = max(tmp,g[k][j] + num[i][k - 1]);

				if (num[i][k - 1] <= j) tmp = max(tmp,g[k][j - num[i][k - 1]]);

				g[i][j] = max(g[i][j],tmp);

			}

		}

	//REP(i,tot) REP(j,n) printf("f[%d][%d] = %d\n",i,j,f[i][j]);

	int ans = 0;

	for (int i = 0; i <= n; i++)

		ans = max(ans,min(i,f[tot][i]));

	printf("%d\n",ans);

	for (int len = tot; len; len--)

		for (int l = 1; l + len - 1 <= tot; l++){

			int r = l + len - 1,y = num[r + 1][tot];

			F[l][r] = max(F[l - 1][r],F[l][r + 1]);

			for (int x = 0; x <= num[1][l - 1]; x++){

				while (y > 0 && cal(l,r,x,y - 1) >= cal(l,r,x,y)) y--;

				F[l][r] = max(F[l][r],cal(l,r,x,y));

			}

		}

	REP(i,n) printf("%d\n",F[L[i]][R[i]]);

}

int main(){

	n = read();

	REP(i,n){

		b[++bi] = L[i] = read();

		b[++bi] = R[i] = read() + L[i] - 1;

	}

	sort(b + 1,b + 1 + bi); tot = 1;

	for (int i = 2; i <= bi; i++) if (b[i] != b[tot]) b[++tot] = b[i];

	REP(i,n){

		L[i] = getn(L[i]),R[i] = getn(R[i]);

		for (int l = L[i]; l; l--)

			for (int r = R[i]; r <= tot; r++)

				num[l][r]++;

	}

	//REP(i,n) printf("[%d,%d]\n",L[i],R[i]); puts("");

	//printf("%d\n",num[3][5]);

	work();

	return 0;

}

巴特西

BZOJ2436 [Noi2011]Noi嘉年华【dp】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ2436 [Noi2011]Noi嘉年华 【dp】

题目链接

题解

最新文章

热门文章

BZOJ2436 [Noi2011]Noi嘉年华【dp】