自动搬运

查看原文

来自洛谷，原作者为

	Ebola 来证个定理吧！

搬运于2025-08-24 22:01:24，当前版本为作者最后更新于2018-10-20 11:59:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题的误导性极强，看到题大部分人都会去想凸包、单调栈一类的东西

显然的有这么一个事实：若游戏的区间是$[l, r]$，那么$r$号亭子必然需要放一个保镖

于是我们确定右端点，然后可以从右往左扫，记$p$表示$r$号亭子能看到的最左边的亭子。然后扫的过程中，用一个sum记录p及其右边部分的答案。因为r最左端能看到的点是$p$，所以$p-1$的纵坐标必然低于$p$，所以对于$[l, p-1]$这一段，我们必然要在$p$或$p-1$中选一个放置保镖，故有：

$f_{l,r}=sum+\min(f_{l,p-1},f_{l,p})$

在扫的过程中，$p$和$sum$也是需要更新的，若当前点是$r$号亭子可见的，那么必然要在之前的$p$和$p-1$中选一个放置保镖，所以$sum$要加上$\min(f_{l+1,p-1},f_{l+1,p})$，然后将$p$更新至当前的$l$

考虑可见性判定，显然只要$l$与$r$的连线，比$p$与$r$的连线斜率更大，$l$就是可见的

就这样，做完了……如果想的方向对了真的非常简单

#include<bits/stdc++.h>
using namespace std;

const int N=5010;
int f[N][N],h[N],n;

double slope(int l,int r){return (double)(h[r]-h[l])/(r-l);}
bool cansee(int l,int x,int r){return slope(x,r)>slope(l,r);}

int main()
{
    int ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",h+i);
    for(int r=1;r<=n;r++)
    {
        ans^=(f[r][r]=1);
        int sum=1,p=0;
        for(int l=r-1;l>=1;l--)
        {
            if(!p||cansee(l,p,r)) sum+=min(f[l+1][p-1],f[l+1][p]),p=l;
            ans^=(f[l][r]=sum+min(f[l][p-1],f[l][p]));
        }
    }
    cout<<ans<<endl;
    return 0;
}