Location>code7788 >text

P1973 [NOI2011] NOI Carnival

Popularity:823 ℃/2024-07-30 21:23:43

Thoughts:

The time is first discretized by setting the total time to be\(cnt\), and then consider solving for\(W(l,r)\), i.e., during the time period\([l,r]\) All programs within can be\(n^2\) The prefixes and, also\(n^3\) Violence.

Then define\(f_{i,j}\) preindex\(i\) One time, site one has\(j\) The state transfer equation for the maximum number of programs in Venue 2 at the time of a program is:

\[f_{i,j} = \max\limits_{k=0}^{i-1} \max(f_{k,j} + W(k,i),f_{k,j-W(k,i)}) \]

Then it can be obtained:

\[ans_0 = \max\limits_{i=0}^n \min(i,f_{cnt,i}) \]

Then the time complexity of the first question is\(O(N^3)\)

Then look at the second question, which requires the definition of\(g_{i,j}\) indicate\(i \sim cnt\) of the time period, site one has\(j\) The state transfer equations are similar for the maximum number of programs in venue two at the time of a program:

\[g_{i,j} = \max\limits_{k=i+1}^{cnt} \max(g_{k,j} + W(i,k),g_{k,j-W(i,k)}) \]

Then define\(dp_{l,r}\) Indicates that if you force the selection of\([l,r]\) of the locally optimal solution for the full program, it is possible to enumerate how many of the left and right number one fields are shifted:

\[dp_{l,r} = \max\limits_{i=0}^n \max\limits_{j=0}^n \min(i+W(l,r)+j,f_{l,i} + g_{r,j}) \]

Then at this point, if you force the selection of\([l,r]\) The answer to the question, which is\(dp_{l,r}\) Is it? The answer is clearly no.

on account of\(f_{l-1,i}\) respond in singing\(g_{r+1,j}\) Only guaranteed\(1 \sim l-1,r+1 \sim j\) of the local optimum, i.e., there may be some activity at one end of the\([l,r]\) Inside, but not at the other end\([l,r]\) Within, it may be better to pick these programs at this point.

So we need to enumerate a\([L,R]\)makes\([L,R]\) embody\([l,r]\)former situation\([l,r]\) The answer to the forced choice is:

\[\max_{L=1}^l \max_{R=r}^{cnt} dp_{L,R} \]

Therefore, as soon as we find\(dp\)It's all right.\(O(N^3)\) of getting answers.

But the calculation\(dp\) The time complexity of\(O(N^4)\), and the constants are large and need to be optimizedMaster Kachan should be able to punch through.

perceive\(f_{l,i}\) cap (a poem)\(g_{r,j}\) Yes, it does.\(i/j\) that do not increase with the increase of the

now\(i\) does not move, then for\(j\) as far as sth. is concerned\(i+W(l,r)+j\) is monoincremental.\(f_{l,i} + g_{r,j}\) is single descending, so\(H(y)=\min(i+W(l,r)+j,f_{l,i} + g_{r,j})\) is a one-peaked function and we need to find its maximum value.

Therefore, we can do the same for\(j\) Perform a pointer walk from\(yjn\) To begin, if\(H(j-1)\ge H(j)\)This will make it possible for the\(j \gets j - 1\)

Here's what needs to be proven in the\(i\) Increase when\(j\) of the single-peaked function will only translate to the left because that's how you can walk the pointer:

exist\(i\) Increase when\(i+W(l,r)+j\) It will also increase.
as for\(f_{l,i}+g_{r,j}\) No additions.
Therefore, the peak point will be shifted left.

The total time complexity is\(O(N^3)\)

Full Code:

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N=205,M=410,INF=1e9; 
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
struct Seg{
	int l,r;
	int id;
}A[N];
int n,cnt,Max;
int ans[N],s[N],h[M];
int F[M][N],G[M][N],dp[M][M],W[M][M];
int get(int i,int j,int l,int r){
	return min(i+W[l][r]+j,F[l][i]+G[r][j]);
}
bool End;
int main(){
//	open("","");
	n=read();
	for(int i=1;i<=n;i++){
		A[i].l=read(),A[i].r=A[i].l+read();
		A[i].id=i;
		h[++cnt]=A[i].l;
		h[++cnt]=A[i].r;
	}
	sort(h+1,h+cnt+1);
	cnt=unique(h+1,h+cnt+1)-(h+1);
	for(int i=1;i<=n;i++){
		A[i].l=lower_bound(h+1,h+cnt+1,A[i].l)-h;
		A[i].r=lower_bound(h+1,h+cnt+1,A[i].r)-h;
	}
	for(int l=1;l<=cnt;l++)
	  for(int r=l;r<=cnt;r++)
	    for(int i=1;i<=n;i++)
	      if(l<=A[i].l&&A[i].r<=r)
	        W[l][r]++;
	for(int i=0;i<=cnt;i++)
	  for(int j=0;j<=n;j++)
	    F[i][j]=-INF;
	F[0][0]=0;
	for(int i=1;i<=cnt;i++)
	  for(int j=0;j<=n;j++)
		for(int k=0;k<i;k++)
		  F[i][j]=max({F[i][j],F[k][j]+W[k][i],(j>=W[k+1][i])?(F[k][j-W[k][i]]):(-INF)});
	for(int i=1;i<=cnt+1;i++)
	  for(int j=0;j<=n;j++)
	    G[i][j]=-INF;
	G[cnt+1][0]=0;
	for(int i=cnt;i>=1;i--)
	  for(int j=0;j<=n;j++)
		for(int k=i+1;k<=cnt+1;k++)
		  G[i][j]=max({G[i][j],G[k][j]+W[i][k],(j>=W[i+1][k])?(G[k][j-W[i][k]]):(-INF)});
	for(int l=1;l<=cnt;l++){
	    for(int r=l;r<=cnt;r++){
	    	for(int x=0,y=n;x<=n;x++){
	    		while(y&&get(x,y-1,l,r)>=get(x,y,l,r))
	    		  y--;
	    		dp[l][r]=max(dp[l][r],get(x,y,l,r));
			}
		}
	}
	for(int i=0;i<=n;i++)
	  ans[0]=max(ans[0],min(i,F[cnt][i]));
	for(int i=1;i<=n;i++)
	  for(int L=1;L<=A[i].l;L++)
		for(int R=A[i].r;R<=cnt;R++)
		  ans[i]=max(ans[i],dp[L][R]);
	for(int i=0;i<=n;i++){
		write(ans[i]);
		putchar('\n');
	}
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}