APIO2015巴厘岛的雕塑——数位DP

题目：https://www.luogu.org/problemnew/show/P3646

对于A>1，将答案各位全置1，然后从高位到低位改成0判断是否可行；

用f[i][j]数组代表前i个数分成j组是否可行，转移是枚举最后一段的左端点k，然后看看后面整个一段的和能否满足要求，如果前后都满足就表示i,j状态也可行；

对于A=1，可以贪心地认为分组数量越少越好，所以可行性转化为最优性，省去一维，转移条件同上，取min即可；

先写了个WA一半的版本：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

int n,A,B,len;

ll f2[],ans,s[];

bool f[][];//可行性

bool dp1(ll x)

{

    memset(f,,sizeof f);

    f[][]=;

    for(int i=;i<=n;i++)//前i个数分成j段 <- 前k个数分成j-1段

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

            for(int k=;k<i;k++)//

                if(((s[i]-s[k])|x)==x)f[i][j]|=f[k][j-];

    for(int i=A;i<=B;i++)

        if(f[n][i])return ;

    return ;

}

bool dp2(ll x)

{

//    memset(f2,0x3f,sizeof f2);

    f2[]=;

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

    {

        ll ad=n+;

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

            if(((s[i]-s[j])|x)==x)ad=min(ad,f2[j]);

        f2[i]=ad+;

    }

    return f2[n]<=B;

}

int main()

{

    scanf("%d%d%d",&n,&A,&B);

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

        scanf("%lld",&s[i]);

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

        s[i]+=s[i-];

    for(len = ;(1LL << len) <= s[n];len++);len--;//位数

    if(A!=)

    {

        ans=(ll)(<<(len+));ans--;

        for(int k=len;k>=;k--)//0!

        {

            ll tmp=ans-(ll)(<<k);

            if(dp1(tmp))ans=tmp;

        }

    }

    else

    {

        ans=(ll)(<<(len+));ans--;

        for(int k=len;k>=;k--)

        {

            ll tmp=(ll)ans-(<<k);

            if(dp2(tmp))ans=tmp;

        }

    }

    printf("%lld",ans);

    return ;

}

囧

后来又直接改成别的写法A的，但还是不太明白原来的写法为什么不行，有什么不同。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

int n,A,B,len;

ll f2[],ans,s[];

bool f[][];//可行性

ll dp1()

{

    ans=;

    for(int t=len;t>=;t--)

    {

        ans+=(1LL<<t)-;

        memset(f,,sizeof f);

        f[][]=;

        for(int i=;i<=n;i++)//前i个数分成j段 <- 前k个数分成j-1段

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

                for(int k=;k<i;k++)//

                    if(((s[i]-s[k])|ans)==ans)f[i][j]|=f[k][j-];

        bool fl=;

        for(int i=A;i<=B;i++)fl|=f[n][i];

        if(fl)ans-=(1LL<<t)-;

        else ans++;

    }

    return ans;

}

ll dp2()

{

    ans=;

    for(int t=len;t>=;t--)

    {

        ans+=(1LL<<t)-;

        f2[]=;

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

        {

            ll ad=n+;

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

                if(((s[i]-s[j])|ans)==ans)ad=min(ad,f2[j]);

            f2[i]=ad+;

        }

        if(f2[n]<=B)ans-=(1LL<<t)-;

        else ans++;

    }

    return ans;

}

int main()

{

    scanf("%d%d%d",&n,&A,&B);

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

        scanf("%lld",&s[i]);

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

        s[i]+=s[i-];

    for(len = ;(1LL << len) <= s[n];len++);len--;//位数

    if(A==)printf("%lld",dp2());

    else printf("%lld",dp1());

    return ;

}