题解 P4310 【绝世好题】

· · 题解

先无良宣传一下博客 wwwwww
文章列表 - 核融合炉心 - 洛谷博客

知识点:DP , 奇妙思路 , 暴力枚举(?)

一道绝世好题

上代码:

```cpp #include<cstdio> #include<ctype.h> #include<algorithm> const int MARX = 1e5+10;; //============================================================= int n,ans,a[MARX]; int f[MARX]; //============================================================= inline int read() { int s=1, w=0; char ch=getchar(); for(; !isdigit(ch);ch=getchar()) if(ch=='-') s =-1; for(; isdigit(ch);ch=getchar()) w = w*10+ch-'0'; return s*w; } //============================================================= signed main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(),f[i]=1;//读入并初始化 for(int i=2;i<=n;i++) for(int j=1;j<i;j++) if(a[i] & a[j]) f[i]=std::max(f[i],f[j]+1),//更新f[i]并找到最大值 ans=std::max(ans,f[i]); printf("%d",ans); } ``` --- $O(31\times n)$ $100$分 ```cpp #include<cstdio> #include<algorithm> #include<map> #include<ctype.h> #define lowbit(x) (x)&-(x) const int MARX = 1e5+10; //============================================================= int n,ans,a[MARX]; int bit[40] , f[MARX]; //具体意义见上文 std::map <int,int> log_2; //============================================================= inline int read() { int fl=1,w=0;char ch=getchar(); while(!isdigit(ch) && ch!='-') ch=getchar(); if(ch=='-') fl=-1; while(isdigit(ch)){w=w*10+ch-'0',ch=getchar();} return fl*w; } //============================================================= signed main() { for(int i=0,sum=1;i<=31;i++,sum<<=1) log_2[sum]=i; //预处理log函数 n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) { for(int j=a[i],low=lowbit(j);j;j-=low,low=lowbit(j)) //枚举二进制位更新f[i] f[i]=std::max(f[i],bit[log_2[low]]+1); for(int j=a[i],low=lowbit(j);j;j-=low,low=lowbit(j)) //使用更新过的f[i]更新bit[k] bit[log_2[low]]=std::max(bit[log_2[low]],f[i]); ans=std::max(f[i],ans); //取得最大答案 } printf("%d",ans); } ``` --- $updata\ on\ 2019.8.13

修复了暴力思路的 bug ,
并添加了代码