守卫

6888: 守卫

时间限制: 1 Sec 内存限制: 512 MB
提交: 78 解决: 24
[提交] [状态] [讨论版] [命题人:admin]

题目描述

九条可怜是一个热爱运动的女孩子。这一天她去爬山，她的父亲为了她的安全，雇了一些保镖，让他们固定地呆在在山的某些位置，来实时监视九条可怜，从而保护她。具体来说，一座山可以描述为一条折线，折线的下方是岩石。这条折线有n个折点，每个折点上有一个亭子，第i个折点的坐标是(i,hi)。九条可怜只可能会在亭子处玩耍，那些保镖也只会在亭子处监视可怜。由于技术方面的原因，一个保镖只能监视所有他能看得到的，横坐标不超过他所在位置的亭子。我们称一个保镖能看到一个亭子p，当且仅当他所在的亭子q和p的连线不经过任何一块岩石。特别地，如果这条连线恰好经过了除了p,q以外的亭子，那么我们认为保镖看不到可怜。雇佣保镖是一件很费钱的事情，可怜的父亲希望保镖越少越好。可怜的父亲还希望得到详尽的雇佣保镖的方案，他知道有些亭子可能正在维修，他想对所有的1≤L≤R≤n计算：如果事先已知了只有区间[L,R]的亭子可以用来玩耍(和监视)，那么最少需要多少个保镖，才能让[L,R]中的每一个亭子都被监视到。可怜的父亲已经得到了一个结果，他希望和你核实他的结果是否正确。

输入

第一行输入一个整数n表示亭子的数目。
接下来一行n个整数，第i个整数hi表示第i个亭子的坐标是(i,hi)。

输出

对所有的L≤L≤R≤n计算：如果事先已知了可怜只会在[L,R]这个区间的亭子里面玩耍，那么最少需要多少个保镖，才能让[L,R]中的每一个亭子都被监视到。由于输出量太大，可怜的父亲只要你输出所有[L,R]的答案的异或即可。

样例输入

3
2 3 1

样例输出

提示

如果R−L+1≤2,那么答案显然是1。
如果L=1,R=n,那么答案是2,需要安排两个保镖在(2,3),(3,1)两个位置监视可怜。
对于30%的数据，n≤20。
对于70%的数据，n≤500。
对于100%的数据，n≤5000。
对于100%的数据，1≤hi≤109。

来源/分类

江西OI2018

思路：先预处理每个点前面能看到的点和不能看到的点，然后暴力，固定r，往前扫l,最后异或上ans！

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll ans,h[5015],f[5015][5015];
bool see[5020][5020];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&h[i]);
    }
    for(int i=1;i<=n;i++)
    {
        see[i][i]=false;
        for(int j=i-1,last=0;j>=1;j--)
        {
            if (!last || (h[i]-h[j])*(i-last)<(h[i]-h[last])*(i-j))
            {
                see[i][j]=true;
                last=j;
            }
            else
            {
                see[i][j]=false;
            }
        }
    }
    for(int r=1;r<=n;r++)
    {
        ll cnt=1,lastr=0;
        for(int l=r;l>=1;l--)
        {
            if(see[r][l])
            {
                if(lastr)
                {
                    cnt+=min(f[l+1][lastr],f[l+1][lastr+1]);
                    lastr=0;
                }
            }
            else
            {
                if(!lastr)
                {
                    lastr=l;
                }
                f[l][r]+=min(f[l][lastr],f[l][lastr+1]);
            }
            f[l][r]+=cnt;
            ans^=f[l][r];
        }
    }
    printf("%lld
",ans);
    return 0;
}