P4310 絕世好題 題解

• 2020 年 7 月 8 日
• 筆記
• DP--線性DP, 基礎--位運算

題目描述

分析

第一次看這道題首先想到的就是時間複雜度為\(\ n^{2}\)的求最長上升子序列

    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++){
            if((a[i]&a[j])!=0) f[i]=max(f[i],f[j]+1);
        }
        ans=max(ans,f[i]);
    }

判斷時把條件改一下就好了

但是這一道題的數據範圍達到了\(10^{5}\)，這樣寫會超時

所以我們考慮更優秀的演算法，突破口就是位運算

題目中的操作是按位與，所以我們可以把一個數的每一個二進位位分別拆分進行計算

我們設\(f[i]\)為當前二進位位為\(i\)時滿足要求的最長長度

我們用一個變數\(k\)記錄當前位置的最大狀態

要注意的是，最大狀態要在所有為\(1\)的位中轉移

比如下面這組數據

011

110

100

在轉移到第二位的時候要取一個最大值

最後不要忘了用這個值去更新\(f\)值

程式碼

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,a[maxn],ans;
int f[300];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;++i){
	    int now=1;
		for(int j=0;j<=30;j++){
		    if(a[i]&(1<<j)){
		        now=max(now,f[j]+1);
		    } 
		}
		for(int j=0;j<=30;j++){
		    if(a[i]&(1<<j)){
		        f[j]=max(f[j],now);
		    }
		}
       ans=max(ans,now);
	}
	printf("%d\n",ans);
	return 0;
}