状态压缩 dp 变式-JZTXT

动态的状态压缩 dp

\(dp_{i, x}\) 表示 \(a_{i-k+1} \cdots a_i\) 所表示的二进制数（0 为没有被选择，1 为已经被选择）
这就会不断删除最后一个，不断加入第一个，可以通过位运算或取模来 \(O(1)\) 计算
不断修改，在中途计算答案

点击查看代码

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <set>

using namespace std;
using LL = long long;
using PII = pair<int, int>;

const int MAXN = 1e5 + 3, MAXK = 300 + 3;

int n, k;
int a[MAXN];
int dp[MAXN][MAXK];

int gcd(int A, int B){
    return !B ? A : gcd(B, A % B);
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  int ANS = 0;
  for(int i = 1; i <= n; i++){
    for(int j = 0; j < (1ll << k); j++){
      int _j = (j * 2) % (1ll << k);
      dp[i][_j] = max(dp[i][_j], dp[i - 1][j]);
      ANS = max(ANS, dp[i][_j]);
    }
    for(int _k = 1; i - _k >= 1 && _k <= k; _k++){
      int _i = i - _k;
      if(gcd(a[i], a[_i]) > 1) continue;
      for(int j = 0; j < (1ll << k); j++){
        if((j >> (_k - 1)) % 2 == 0){
          int _j = ((j + (1ll << (_k - 1))) * 2 + 1) % (1ll << k);
          dp[i][_j] = max(dp[i][_j], dp[i - 1][j] + 1);
          ANS = max(ANS, dp[i][_j]);
        }
      }
    }
  }
  cout << ANS;
  return 0;
}