即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

BZOJ4300[绝世好题]题解–DP

编程语言 CHNWJD 21℃ 0评论

【链接】


bzoj4300

【题目大意】


给你一个数列a,求a的子序列b,是bi&bi-1!=0。

【解题报告】


首先我们有个笨蛋的想法,就是n^2枚举当前状态和上一状态刷DP。但是时间复杂度似乎扛不住。所以就要换一个思路,bi&bi-1!=0,不就是两个数在二进制下相对应的位置至少有一个位置都是1。所以定义f[i]表示二进制下所对应的第i位是1的最长子序列。如果当前推到第i个数,则从所对应的二进制是1的位置刷目前所得到的最大值,然后将这个最大值赋给二进制下是1的位置。答案就是max(f[0~30])(最多也就31位),复杂度就降到了O(30*n)。

#include
#include
#include
using namespace std;
const int maxn=33;
int n,ans,f[maxn];
inline int Read()
{
    int res=0;
    char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') res=res*10+ch-48,ch=getchar();
    return res;
}
int main()
{
    freopen("4300.in","r",stdin);
    freopen("4300.out","w",stdout);
    memset(f,0,sizeof(f));
    n=Read(); ans=0;
    for (int i=1; i<=n; i++)
    {
        int x=Read(),Max=0;
        for (int j=x,k=0; j; j>>=1,k++) if (j%2) Max=max(Max,f[k]);
        for (int j=x,k=0; j; j>>=1,k++) if (j%2) f[k]=Max+1;
    }
    for (int i=0; i<=30; i++) ans=max(ans,f[i]);
    printf("%d",ans);
    return 0;
}

转载请注明:CodingBlog » BZOJ4300[绝世好题]题解–DP

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情