2023.8.8
P4310 绝世好题
首先可以想到的90pts做法是最长上升子序列dp，然后就考虑一下优化。这个做法要进行的转移过多，我们考虑怎么减少转移次数。由 & 运算我们可以发现，能转移到当前数的 \(a[j]\) ， 必然和当前数 \(a[i]\) 至少有一个二进制数位上同时为 1。因此我们就可以定义 \(bit[i]\) 表示到当前数第 \(i\) 位为 1 的最长子序列长度，定义一个 \(Max\) ，再枚举当前数的每一个二进制位 \(k\) , 若第 \(k\) 位为1， $Max = max(Max, bit[k] + 1) $， 最后将转移所涉及到的 \(bit[k] = Max\) 即可。
code:
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define N 35
int n, ans = 0;
int f[N];
int main(){
// freopen("shuju.in", "r", stdin);
// freopen("shuju.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++){
unsigned int a;
cin >> a;
int maxf = 0;
for(int j = 0; j < 32; j ++){
if(a & (1 << j)){
maxf = max(maxf, f[j] + 1);
}
}
for(int j = 0; j < 32; j ++){
if(a & (1 << j)){
f[j] = maxf;
}
}
}
for(int j = 0; j <= 31; j ++){
ans = max(ans, f[j]);
}
cout << ans;
}
P6647 [CCC2019] Tourism
给出一段数列，每次从中还未取过的 \(k\) 个数，最多取 \(t\) 次，求这 \(t\) 次每次 \(k\) 个数的最大值之和的最大值。