[JXOI 2018] 守卫 解题报告 (DP)

interlinkage:

https://www.luogu.org/problemnew/show/P4563

description:

solution:

• 注意到对于范围$[l,r]$，$r$这个亭子一定要设置保镖
• 设$f_{l,r}$为活动范围为$[l,r]$所需的最小保镖数
• 枚举右端点$r$，然后从右向左遍历左端点$l$。设$p$为在$[l,r]$中$r$处能看到的最左的点
• 这样的话我们就必须在$p$或者$p-1$处放置保镖
• 于是$f_{l,r}=min(f_{l,p-1},f_{l,p})+f_{p+1,r}$
• 注意一下$p$的更新，若$l$到$r$连线的斜率小于$p$到$r$连线的斜率，那么就要更新$p=l$了

code:

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<iostream>

#include<cmath>

using namespace std;

const int N=+;

int n;

int h[N],f[N][N];

inline int read()

{

    char ch=getchar();int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

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

bool cansee(int l,int p,int r)

{

    return slope(l,r)<slope(p,r);

}

int main()

{

    n=read();

    for (int i=;i<=n;i++) h[i]=read();

    int ans=;

    for (int r=;r<=n;r++)

    {

        f[r][r]=;ans^=f[r][r];

        int p=;

        for (int l=r-;l>=;l--)

        {

            if (!p||cansee(l,p,r)) p=l;

            f[l][r]=min(f[l][p-],f[l][p])+f[p+][r];

            ans^=f[l][r];

        }

    }

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

    return ;

}