链接：https://loj.ac/problem/2545

题目描述

九条可怜是一个热爱运动的女孩子。

这一天她去爬山，她的父亲为了她的安全，雇了一些保镖，让他们固定地呆在在山的某些位置，来实时监视九条可怜，从而保护她。

具体来说，一座山可以描述为一条折线，折线的下方是岩石。这条折线有  个折点，每个折点上有一个亭子，第  个折点的坐标是  。九条可怜只可能会在亭子处玩耍，那些保镖也只会在亭子处监视可怜。

由于技术方面的原因，一个保镖只能监视所有他能看得到的，横坐标不超过他所在位置的亭子。我们称一个保镖能看到一个亭子  ，当且仅当他所在的亭子  和  的连线不经过任何一块岩石。特别地，如果这条连线恰好经过了除了  以外的亭子，那么我们认为保镖看不到可怜。

雇佣保镖是一件很费钱的事情，可怜的父亲希望保镖越少越好。

可怜的父亲还希望得到详尽的雇佣保镖的方案，他知道有些亭子可能正在维修，他想对所有的  计算：如果事先已知了只有区间  的亭子可以用来玩耍(和监视)，那么最少需要多少个保镖，才能让  中的每一个亭子都被监视到。

可怜的父亲已经得到了一个结果，他希望和你核实他的结果是否正确。

输入格式

第一行输入一个整数  表示亭子的数目。 接下来一行  个整数，第  个整数  表示第  个亭子的坐标是  。

输出格式

对所有的  计算：如果事先已知了可怜只会在  这个区间的亭子里面玩耍，那么最少需要多少个保镖，才能让  中的每一个亭子都被监视到。由于输出量太大，可怜的父亲只要你输出所有  的答案的异或即可。

样例

样例输入

3
2 3 1

样例输出

3

样例解释

如果  ,那么答案显然是  。 如果  ,那么答案是  ,需要安排两个保镖在  两个位置监视可怜。

数据范围与提示

对于  的数据，  。
对于  的数据，  。
对于  的数据，  。
对于  的数据，  。

 

思路：首先我们可以通过求斜率得出一个点是否覆盖另一个点。对于L到R的区间来说，对于这一段结果有影响的是从顶点开始到所有可达的点的影响，进而可以转换成将整个区间分割成好多块，然后每一块求出来最优然后就是对于当前这个大的区间的一种最优的情况。因为加入顶点可以看到某个点就可以考虑那个点是否需要一定放一个人来守卫，这样就不断优化区间，dp[j+1][l-1] 就是考虑那种可以不放守卫，顶点也可以来看到当前点的可以使减少一个放守卫的人数。

代码：

#include<bits/stdc++.h>

using namespace std;

int a[5001];

int dp[5001][5001];

int check(int l,int mid,int r)//比较斜率判断一个点是否会遮挡另一个点

{

return (a[r]-a[mid])/(r-mid) > (a[r]-a[l])/(r-l);

}

int main()

{

int n;

scanf("%d",&n);

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

scanf("%d",&a[i]);

int ans=0;

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

{

dp[i][i]=1;//对于任何一点L-r的区间 r肯定要放一个

int sum=1;//假设sum表示当前 l-r 需要的保镖的最小数量

int l=i; //初始化为当前最远点

ans = ans^dp[i][i];

for(int j=i-1;j>=1;j--)

{

if(l==i||check(j,l,i))//是否第一个点或者是否挡住

{

sum = sum + min(dp[j+1][l-1],dp[j+1][l]);

l=j;

}

dp[j][i] = sum + min(dp[j][l-1],dp[j][l]);//如果借助看不到当前点就考虑那个点到l之间的最优解因为l之后已经是最优的解

ans^=dp[j][i];//对于每个区间都进行^运算

}

}

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

return 0;

}