题解 P4310 【绝世好题】

· · 题解

苹果叶万岁 !!!

此题80分做法就是纯DP,

即f[i]=max{f[j]+1}且j<i且b[i]&b[j]!=0

i从1~n枚举i,j从1~i-1枚举j

这么简单就80分了,不骗分都说不过去啊

那么,100分的代码是什么咧,其实很简单,哦,

其实&的结果最重要的是看两位二进制是否均为1,如果均为1那么&的结果为1,否则为0

那就很好办了,我就搞一个数组f来进行 dynamic programme ,i从1~n枚举每个数,然后枚举这个数的二进制的每一位。

如果某个数二进制的第j位是1,那么f[j]++;f[j]表示到当前状态最后一个数为止的二进制的第j位满足条件的最长子序列长度。

然后将所有等于1的位的f值都换成所有等于1的位上f的最大值即可。

为什么可以换成最大值咧 ?因为一个数的满足条件的二进制位上的f值可以被转移到所有满足条件的二进制位上。

有的同学要问了,怎样求某个数二进制的第i位咧？这时候位运算就闪亮登场了。x&(1<<i)即可求出。

举例1(其实就是样例):1 2 3

转为二进制:01 10 11

0.f[0]=0 f[1]=0

1.f[0]=1 f[1]=0

2.f[0]=1 f[1]=1

3.f[0]=2 f[1]=2

ans=2

举例2:1 3 2 4

转为二进制:001 011 010 100

0:f[0]=0 f[1]=0 f[2]=0

1:f[0]=1 f[1]=0 f[2]=0

2:f[0]=2 f[1]=max(f[1]+1=1,f[0]=2)=2,f[2]=0

3:f[0]=2 f[1]=3 f[2]=0

4:f[0]=2 f[1]=3 f[2]=1

ans=3

其实这题还是需要一点思维的哦。

PS:O(nlogn)搞定

Code:


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=35;
int n,ans,f[N],Max;
int main(){
    scanf("%d",&n);
    for(int j=1;j<=n;j++){//枚举每个数
        unsigned int x;//注意了,这里最好用unsigned int
        scanf("%ud",&x);//读入时为%ud
        Max=0;//最大值赋值为0
        for(int i=0;(1<<i)<=x;i++){//枚举这个数的每一位
            if(x&(1<<i)){//重点:如果这一位是1!!!
                Max=max(Max,f[i]+1);//长度++,并取最大进行f值的转移
            }
        }
        for(int i=0;(1<<i)<=x;i++){
            if(x&(1<<i)){//重点:如果这一位是1!!!
                f[i]=Max;//转移
            }
        }
    }
    for(int i=0;i<32;++i){
        ans=max(ans,f[i]);//ans为最长的
    }
    printf("%d\n", ans);
    return 0;
}~~~