【BZOJ5324】[JXOI2018]守卫（动态规划）

【BZOJ5324】[JXOI2018]守卫（动态规划）

题面

BZOJ
洛谷

题解

既然只能看到横坐标在左侧的点，那么对于任意一个区间([l,r])而言，(r)必须被选。
假设(r)看不到若干个区间，其中一个区间是([x,y])，因为(y+1)能够被看到，所以([y+2,r])这一段一定看不到([x,y])。因此(y,y+1)中必须要选择一个。
先预处理出任意两点之间能够互相看到，这个东西的复杂度是(O(n^2))的。
设(f[l][r])表示区间([l,r])的答案。
固定右端点，向左扫，每次求出当前的看不到的区间，那么(f[l][r]=1+sum min(f[x][y],f[x][y+1]))。
这样子的时间复杂度就是(O(n^2))的了。

#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 5050
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int n,ans,a[MAX],f[MAX][MAX];
bool g[MAX][MAX];
int main()
{
	n=read();
	for(int i=1;i<=n;++i)a[i]=read();
	for(int i=1;i<=n;++i)
		for(int j=i-1,lst=0;j;--j)
			if(!lst||1ll*(a[i]-a[j])*(i-lst)<1ll*(a[i]-a[lst])*(i-j))
				g[i][j]=g[j][i]=true,lst=j;
	for(int i=1;i<=n;++i)
		for(int j=i,s=1,lst=0;j;--j)
		{
			if(g[i][j]){if(!g[i][j+1])s+=min(f[j+1][lst],f[j+1][lst+1]);f[j][i]=s;}
			else{if(g[i][j+1])lst=j;f[j][i]=s+min(f[j][lst],f[j][lst+1]);}
			ans^=f[j][i];
		}
	printf("%d
",ans);
	return 0;
}