状压 dp 变式

huangqixuan / 2023-08-07 / 原文

利用 \(dp_i\) 的取值

一开始这就是状压 dp 模版
但是有时间要求，而且又要满足连续时间超过 \(L\)，显然连续时间越大越好
那么 \(dp_i\) 的取值就是最大连续时间
转移时可以根据 \(dp_i\) 进行二分，总时间复杂度能够勉强通过

点击查看代码

#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 = 25 + 3, MAXK = 5e6 + 3;
const LL mod = 1e9 + 7;

struct st_cmp{
  bool operator() (int i, int j) const {
    return i > j;
  }
};

int n, L;
set<int, st_cmp> st[MAXN];
int dp[MAXK], D[MAXN], cnt1[MAXK];

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> L;
  for(int i = 1, C; i <= n; i++){
    cin >> D[i] >> C;
    for(int j = 1, X; j <= C; j++){
      cin >> X, st[i].insert(X);
    }
  }
  for(int i = 1; i < (1ll << n); i++){
    cnt1[i] = cnt1[i ^ (i & (-i))] + 1;
  }
  int ANS = 1e9;
  for(int i = 0; i < (1ll << n); i++){
    for(int j = 0; j < n; j++){
      if((i >> j) % 2 == 0){
        auto s = st[j + 1].lower_bound(dp[i]);
        int _i = i + (1ll << j);
        if(s != st[j + 1].end()){
          dp[_i] = max(dp[_i], *s + D[j + 1]);
          if(dp[_i] > L){
            ANS = min(ANS, cnt1[_i]);
          }
        }
      }
    }
  }
  cout << (ANS >= 1e9 ? -1 : ANS);
  return 0;
}

动态的状压 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;
}

## https://codeforces.com/problemset/problem/165/E