傳送門

首先考慮定下一個端點，然后剩下的就可以遞推了
一開始想的是定下左端點，然后預處理出位置最遠能看到的位置，后來發現時間GG了
看題解發現定右端點優秀得多
記錄下當前\(r\)最遠能看到的位置\(p\)，能看到\([p,r]\)一共需要幾個守衛，這個后綴和一下就好了
然后斜率的判斷，只需要\(l,r\)的斜率小于\(p,r\)的斜率，這個點就可以被看見，這是顯然的，可以畫一下圖
代碼：

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; void read(int &x) {char ch; bool ok;for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x; } #define rg register const int maxn=5010; int n,f[maxn][maxn],a[maxn],ans; int main() {read(n);for(rg int i=1;i<=n;i++)read(a[i]);for(rg int r=1;r<=n;r++){f[r][r]=1;ans^=1;int las=0,sum=1;for(rg int l=r-1;l;l--){if(!las||(double)((a[l]-a[r])/(l-r))<(double)((a[r]-a[las])/(r-las)))sum+=min(f[l+1][las],f[l+1][las-1]),las=l;f[l][r]=sum+min(f[l][las],f[l][las-1]);ans^=f[l][r];}}printf("%d\n",ans); }

轉載于:https://www.cnblogs.com/lcxer/p/10534841.html

總結

以上是生活随笔為你收集整理的bzoj5324:[Jxoi2018]守卫的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。