bzoj 4069: [Apio2015]巴厘岛的雕塑【dp】

居然要对不同的数据写不同的dp= =

首先记得开long long，<<的时候要写成1ll<<bt

根据or的性质，总体思路是从大到小枚举答案的每一位，看是否能为0.

首先对于A=1的情况，因为没有最小值限制，所以设f[i]为到i为止，当前位能为0的最小长度。判断f[n]是否小于等于B即可。注意保证当前位为0的前提下也要保证之前枚举的位不变。时间复杂度是\( O(nlog_2nlog_2ans) \)

对于其他情况（n<=100），设f[i][j]表示枚举到i为止已经分了j段是否能让当前位为0.最后判断是否有f[n][a]~f[n][b]中为ture即可。时间复杂度是\( O(n^2log_2nlog_2ans) \).

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=2005,inf=1e9;

int n,a,b;

long long s[N],bt,ans;

int read()

{

    int r=0,f=1;

    char p=getchar();

    while(p>'9'||p<'0')

    {

        if(p=='-')

            f=-1;

        p=getchar();

    }

    while(p>='0'&&p<='9')

    {

        r=r*10+p-48;

        p=getchar();

    }

    return r*f;

}

bool ok(long long x)

{

    x>>=bt,x<<=bt;

    return (x|ans)==ans;

}

int main()

{

    n=read(),a=read(),b=read();

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

        s[i]=s[i-1]+read();

    for(long long x=s[n];x;x>>=1,bt++);

    if(a==1)

    {

        int f[N];

        for(;bt>=0;bt--)

        {

            f[0]=0;

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

            {

                f[i]=inf;

                for(int j=0;j<i;j++)

                    if(f[i]>f[j]+1&&ok(s[i]-s[j]))

                        f[i]=f[j]+1;

            }

            if(f[n]>b)

                ans|=(1ll<<bt);

        }

    }

    else

    {

        bool f[105][105];

        for(;bt>=0;bt--)

        {

            memset(f,0,sizeof(f));

            f[0][0]=1;

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

                for(int j=1;j<=i&&j<=b;j++)

                    for(int k=0;k<i&&!f[i][j];k++)

                        if(f[k][j-1]&&ok(s[i]-s[k]))

                            f[i][j]=1;

            bool ok=0;

            for(int i=a;i<=b;i++)

                if(f[n][i])

                {

                    ok=1;

                    break;

                }

            if(!ok)

                ans|=(1ll<<bt);

        }

    }

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

    return 0;

}

巴特西

bzoj 4069: [Apio2015]巴厘岛的雕塑【dp】

最新文章

热门文章