BZOJ5324 & 洛谷4563 & LOJ2545：[JXOI2018]守卫—

题目见上。

参考：https://blog.csdn.net/dofypxy/article/details/80196942

区间dp，设f[i][j]为[i,j]的答案，see[i][j]为i是否能看到j。

显然see数组可以O(n^2)处理，通过斜率很容易处理。

然后就是O(n^2)处理f，emm很不好想。

思考当你在[i,j]区间内放保镖的时候，j肯定要放一个保镖，然后对于j看不到的地方，我们视为区间[ii,jj]。

我们给出结论：为了覆盖这个区间，我们一定需要在jj或jj+1处放一个保镖。这个结论很容易证明。

于是我们就有了f[i][j]=sigma(min(f[ii][jj],f[ii][jj+1]))+1。这个递推式是O(n^3)的。

但是因为当j固定时，移动i，其转移方程有重合的部分，于是可以O(n^2)处理，具体可以看代码。

#include<cmath>

#include<queue>

#include<cstdio>

#include<cctype>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef double dl;

const int N=;

const int INF=2e9;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

bool see[N][N];

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

dl slope(int a,int b){

    return (dl)(h[a]-h[b])/(a-b);

}

int main(){

    n=read();h[]=INF;

    for(int i=;i<=n;i++){

    h[i]=read();

    int l,r;

    see[i][i]=see[i][i-]=;

    dl k=slope(i-,i);

    for(int j=i-;j>=;j--){

        while(j&&slope(j,i)>=k){

        see[i][j--]=;

        }

        k=slope(j,i);see[i][j]=;

    }

    }

    int ans=;

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

    int s=,t=;

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

        if(see[r][l]){

        if(!see[r][l-])t=l-;

        f[l][r]=s;

        }else{

        f[l][r]=s+min(f[l][t],f[l][t+]);

        if(see[r][l-])s+=min(f[l][t],f[l][t+]);

        }

        ans^=f[l][r];

    }

    }

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

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

BZOJ5324 & 洛谷4563 & LOJ2545：[JXOI2018]守卫——题解

最新文章

热门文章