标签：变式 int 状压 MAXK MAXN using include dp
- 一开始这就是状压 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_{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
标签：变式,
int,
状压,
MAXK,
MAXN,
using,
include,
dp
From： https://www.cnblogs.com/huangqixuan/p/17612551.html