【JXOI2018】守卫

【JXOI2018】守卫

参考题解：https://blog.csdn.net/dofypxy/article/details/80196942

大致思路就是：区间DP。对于([l,r])的答案，(r)肯定要放守卫，然后(r)不能看到的一些连续区间([l_k,r_k])是相互独立的。所以(f_{l,r}=sum min { f_{l_k,r_k},f_{l_k,r_k+1} }+1)

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 5005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n;
int h[N];
bool see[N][N];
int f[N][N];
int main() {
	n=Get();
	for(int i=1;i<=n;i++) h[i]=Get();
	for(int i=1;i<n;i++) {
		see[i][i+1]=1;
		int id=i+1;
		for(int j=i+2;j<=n;j++) {
			if(1ll*(h[id]-h[i])*(j-i)<1ll*(h[j]-h[i])*(id-i)) {
				see[i][j]=1;
				id=j;
			}
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			f[i][j]=1e9;
	for(int i=1;i<=n;i++) {
		f[i][i]=1;
		int last=0,sum=0;
		int id=i;
		for(int j=i-1;j>=1;j--) {
			if(see[j][i]) {
				sum+=last;
				id=j;
			}
			last=min(f[j][id],f[j][id-1]);
			f[j][i]=sum+last+1;
		}
	}
	
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			ans^=f[i][j];
	cout<<ans;
	return 0;
}