Codeforces1208 F. Bits And Pieces (SOS DP)

本文主要是介绍Codeforces1208 F. Bits And Pieces (SOS DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
寻找最大的a[i]|a[j]&a[k]，满足i<j<k。

思路：
SOS DP。

定义$dp[sta][0/1]$得到$sta$这个状态的最大下标，次大下标。
那么初始有$dp[a[i]][0]=i$。对于a[j]&a[k]，是指就是求$a[j]$的子集或者$a[k]$的子集。所以可以用SOS DP的方法维护出$sta$状态的最大次大下标。

对于$dp[sta][1]$，就代表通过与运算得出$sta$状态（a[j]&a[k]状态的子集）的次大下标。

那么我们枚举$a[i]$，要使得结果最大，就要尽可能保证满足取到二进制最高位。那么对于$a[i]$已有的位不需要考虑，然后按照最高位往低，一位一位的考虑看$dp[sta][1]$是否大于$i$，如果大于说明能取到a[j]&a[k]为$sta$状态超集，且$j>i$。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>using namespace std;
typedef long long ll;const int maxn = 6e6 + 7;
int a[maxn],dp[maxn][2];
int n;void insert(int sta,int pos) {if(pos > dp[sta][0]) {dp[sta][1] = dp[sta][0];dp[sta][0] = pos;} else if(pos > dp[sta][1]) {dp[sta][1] = pos;}
}void init() {for(int i = 1;i <= n;i++) insert(a[i],i);for(int i = 0;i <= 21;i++) {for(int j = 0;j <= 2e6;j++) {if(j & (1 << i)) {insert(j ^ (1 << i),dp[j][0]);insert(j ^ (1 << i),dp[j][1]);}}}
}bool judge(int sta,int pos) {if(dp[sta][1] > pos) {return true;}return false;
}int main() {scanf("%d",&n);for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);}init();int mx = 0;for(int i = 1;i <= n - 2;i++) {int num = 0;for(int j = 21;j >= 0;j--) {if(a[i] & (1 << j)) {continue;}if(judge(num ^ (1 << j),i)) num ^= (1 << j);}mx = max(mx,num | a[i]);}printf("%d\n",mx);return 0;
}

这篇关于Codeforces1208 F. Bits And Pieces (SOS DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---