[bzoj3126][USACO2013]Photo_动态规划

Photo bzoj-3126

题目大意：给你一个n长度的数轴和m个区间，每个区间里有且仅有一个点，问最多能有多少个点。

注释：$1\le n \le 2\cdot 10^5$，$1\le m\le10^5$。

想法：开始和GXZlegend在那里贪心。贪了挺久发现几乎所有的贪心策略都会被卡，此题被当做毒瘤题。然后上bz上找题解发现了新大陆？？

　　这题是一个dp。

　　状态：dp[i]表示第i个位置必须放点，最多能在前i个位置放多少点。

　　转移：我们记录几个事儿。首先，R[i]表示所有区间中包含i且左端点最大的区间的左端点坐标。L[i]表示所有取件中右端点在i左侧且左端点最大的左端点坐标。关于L和R的更新显然是容易的，我们只需要再每加进来的区间里更新即可。然后转移方程就是f[i] = max { f[j] } + 1 ( L[i]<=j<=R[i] ) 。这个过程可以用单调队列来优化。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#define N 200003

using namespace std;

int n,m,L[N],R[N];

int head,tail,q[N],f[N];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n+1;i++) R[i]=i-1;

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

	{

		int x,y; scanf("%d%d",&x,&y);

		R[y]=min(R[y],x-1);

		L[y+1]=max(L[y+1],x);

	}

	for(int i=n;i>=1;i--) R[i]=min(R[i+1],R[i]);

	for(int i=2;i<=n+1;i++) L[i]=max(L[i-1],L[i]);

	int j=1; head=tail=1; q[1]=0;

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

	{

		while(j<=R[i]&&j<=n)

		{

			if(f[j]==-1)

			{

				j++;

				continue;

			}

			while(f[j]>f[q[tail]]&&head<=tail) tail--;

			q[++tail]=j;

			j++;

		}

		while(q[head]<L[i]&&head<=tail) head++;

		if(head<=tail) f[i]=f[q[head]]+(i!=n+1?1:0);

		else f[i]=-1;

	}

	printf("%d\n",f[n+1]);

}

　　小结：贪心显然的题大部分好像都不是贪心，因为dp实在是太tm强了。

巴特西

[bzoj3126][USACO2013]Photo_动态规划_单调队列

最新文章

热门文章