Luogu

BZOJ

分析

区间DP+九条可怜

首先发现一条性质:对于一个区间 $[l,r]$ ,显然必须要在 $r$ 处放一个保镖。

设 $f[i][j]$ 表示 $[i,j]$ 的答案。

考虑让右端点从右往左扫,然后设 $p$ 为 $r$ 能看到的最左边的位置, $sum$ 表示 $p$及其右边部分的答案。

容易知道 $p-1$ 的纵坐标必然低于 $p$ ,于是一定要在 $p-1$ 或 $p$ 的地方放一个保镖,容易得到 $f[i][j]=sum+\min\left\{f[i+1][p-1],f[i+1][p]\right\}$。

在扫的过程中,需要同时更新 $p$ 和 $sum$ 。以及边界为 $f[i][i]=1$ 。

最后来考虑怎么判定可见性。容易发现,如果直线 $(i,j)$ 的斜率比直线 $(p,j)$ 的斜率大,那么 $j$ 就能看见 $i$ 。

细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=5000+10;

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

inline double slope(int i,int j) { return 1.0*(h[i]-h[j])/(i-j); }
inline int check(int p,int i,int j) { return slope(p,j)>slope(i,j); }

int main() {
    n=read();
    for (re int i=1;i<=n;++i) h[i]=read();
    for (re int j=1;j<=n;++j) {
        f[j][j]=1; int sum=1,p=0;
        for (re int i=j-1;i>=1;--i) {
            if (!p||check(p,i,j))
                sum+=min(f[i+1][p-1],f[i+1][p]),p=i;
            f[i][j]=sum+min(f[i][p-1],f[i][p]);
        }
    }
    int ans=0;
    for (re int i=1;i<=n;++i)
        for (re int j=i;j<=n;++j)
            ans^=f[i][j];
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 14 PM