前往：我自己搭建的博客
題目
洛谷P4310絕世好題
題解
相鄰兩數位與不為0，等價于兩數存在一個二進制位都為1，若只考慮某一個二進制位，則所有此位為1的數構成了最長子序列，再將所有二進制位綜合考慮，使用動態規劃，f[i]表示以上一個第i位為1的數為結尾的最長子序列的長度，若當前數的第i位為0，則不作更新；若為1，則選一個最大的f[j]更新，
代碼
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6;
int n;
int f[32],a[maxn];
inline void dp()
{
for(int i=1;i<=n;i++)
{
int mx=0;
for(int j=0;j<=30;j++) if(a[i]&(1<<j)) mx=max(mx,f[j]+1);
for(int j=0;j<=30;j++) if(a[i]&(1<<j)) f[j]=mx;
}
}
int main()
{
scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]);
dp(); int ans=0;
for(int i=0;i<=30;i++) ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/44633.html
標籤：其他
上一篇：C#：類與物件_創建玩家類