首页 > 其他 > 详细

【BZOJ5324】[JXOI2018]守卫(动态规划)

时间:2019-02-23 16:54:56      阅读:210      评论:0      收藏:0      [点我收藏+]

【BZOJ5324】[JXOI2018]守卫(动态规划)

题面

BZOJ
洛谷

题解

既然只能看到横坐标在左侧的点,那么对于任意一个区间\([l,r]\)而言,\(r\)必须被选。
假设\(r\)看不到若干个区间,其中一个区间是\([x,y]\),因为\(y+1\)能够被看到,所以\([y+2,r]\)这一段一定看不到\([x,y]\)。因此\(y,y+1\)中必须要选择一个。
先预处理出任意两点之间能够互相看到,这个东西的复杂度是\(O(n^2)\)的。
\(f[l][r]\)表示区间\([l,r]\)的答案。
固定右端点,向左扫,每次求出当前的看不到的区间,那么\(f[l][r]=1+\sum min(f[x][y],f[x][y+1])\)
这样子的时间复杂度就是\(O(n^2)\)的了。

#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 5050
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int n,ans,a[MAX],f[MAX][MAX];
bool g[MAX][MAX];
int main()
{
    n=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)
        for(int j=i-1,lst=0;j;--j)
            if(!lst||1ll*(a[i]-a[j])*(i-lst)<1ll*(a[i]-a[lst])*(i-j))
                g[i][j]=g[j][i]=true,lst=j;
    for(int i=1;i<=n;++i)
        for(int j=i,s=1,lst=0;j;--j)
        {
            if(g[i][j]){if(!g[i][j+1])s+=min(f[j+1][lst],f[j+1][lst+1]);f[j][i]=s;}
            else{if(g[i][j+1])lst=j;f[j][i]=s+min(f[j][lst],f[j][lst+1]);}
            ans^=f[j][i];
        }
    printf("%d\n",ans);
    return 0;
}

【BZOJ5324】[JXOI2018]守卫(动态规划)

原文:https://www.cnblogs.com/cjyyb/p/10423046.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!