守卫

本文主要是介绍守卫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

守卫

题解

这道题是一个区间dp。若中必须放一个点才能看完这个区间。

我们先确定右端点，  然后从左往右扫，记p为r能看到的最左端的点。在扫的过程中，用sum记录p及其右的答案。r最左边只能看到p，所以p-1 的纵坐标必定小于p即中，p与p-1中必定有一个点被选。

因此dp式为

扫的过程中，需要更新sum与p。sum更新后，把p更为l。

只要，l就可见

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream> 
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
#define gc() getchar()
LL n,h[5005],dp[5005][5005],ans;
template<typename _T>
inline void read(_T &x)
{_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
double slope(LL l,LL r)
{return (1.0*(h[r]-h[l]))/(1.0*(r-l)); 
}
bool query(LL a,LL b,LL c)
{return slope(c,a)<slope(b,c);
}
int main()
{read(n);for(int i=1;i<=n;i++) read(h[i]);for(int i=1;i<=n;i++) dp[i][i]=1,ans^=1;//初始化for(int i=1;i<=n;i++){LL sum=1,p=0;for(int j=i-1;j>0;j--){if(query(j,p,i)||p==0) sum+=min(dp[j+1][p-1],dp[j+1][p]),p=j;//更新sum与pdp[j][i]=sum+min(dp[j][p-1],dp[j][p]);//dp从i到j的区间ans^=dp[j][i];//ans异或dp值//printf("%d %d:%d\n",j,i,dp[j][i]);}}printf("%lld",ans);return 0;
}

谢谢！！！

这篇关于守卫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---