2021 ICPC 澳门站G Cyclic Buffer （特殊的状压dp）

本文主要是介绍2021 ICPC 澳门站G Cyclic Buffer （特殊的状压dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

G Cyclic Buffer

链接：The 2021 ICPC Asia Macau Regional Contest
介绍一种特殊的状态压缩dp（自己取的名字），不同于一般的二进制状压dp。在递推dp中一般转移都是连续的从 $\rightarrow i+1$ ，而当一些状态相同在题目中时我们就可以跳跃转移 $i\rightarrow j$ ，这中间的状态都被压缩了。详情可以看题解。

题意

给定长度为 $n$ 的排列 $p_i$ ，可以访问 $1\sim k$ 位置上的任意元素，并且有两个操作，一个是将数组所有元素右移一格，此时 $p_n \rightarrow p_1$ ，或者左移一格，此时 $p_1\rightarrow p_n$ . 每个操作都需要花费 $1$ 代价。你想要顺序的从 $1\sim n$ 访问所有元素，问最小的代价。

法一（特殊的状压dp）

法一解法参考知乎大佬cup-pyy的博客第46届ICPC东亚洲区域赛(澳门)题解

贪心的不难考虑到，如果当前我需要访问的 $i$ 的位置 $\geq k$ ，那么我们只有两个选择，移动数组使 $i$ 移动到 $1/ k$ 位置上，多移动不一定会是最优的，但不移动一定可以转移到最优的，那么此时就有两个状态 $f [i] [0/ k]$ ，代表将 $i$ 元素移动到 $1/ k$ 位置上的最小花费。

那么还有一个问题，若是当前元素 $i$ ，在上一个元素 $i - 1$ 移动到 $1/ k$ 时已经在 $1\sim k$ 上了怎么转移呢，强行转移到 $1/ k$ 位置上吗，但可能不动才是最优的。此时就需要将状态压缩一下了，若是我们知道此时 [大于 $i - 1$ 的] [最小的] [不在 $1\sim k$ 位置上的] 元素 $j$ 是什么，我们就可以以将 $f[i-1]\sim f[j-1]$ 压缩为同一个状态，直接从 $f[i-1]\rightarrow f[j]$ .

这样我们需要预处理出 $p [i] [0/1]$ : 元素 $i$ 移动到 $1/ k$ 位置上时，大于 $i$ 的最小的不在 $1\sim k$ 位置上元素 $j$ .

可以用线段树维护元素 $i$ 是否在 $1\sim k$ 位置上，查询就是找 $i+1\sim n$ 区间内第一个为 $0$ 的数，数组每次右移一格也只要两次单点修改即可，具体见代码。

/*
f[n][2]:第i个数，恰好在 1/k 位置上取到的最小花费考虑当将i移动到1/k后，发现数字i+1已经在1~k的位置上如何处理，直接移动到1/k肯定不会最优，但也无法保存状态。
我们考虑一种另类的状压，既然当前数字已经在1~k上那么将其与 f[i][0/k] 合并压缩， 若是后面有很多数字都有这样的情况也都一并压缩
直到出现一个数字j位置pos > k, 那么此时我们就可以转移 f[i][0/k] -> f[j][0/k]需要预处理出数字i在1/k位置上时，下一个最小的大于i的不在1~k上的数
*/#include <bits/stdc++.h>
using namespace std;#define ls p << 1
#define rs p << 1 | 1
#define ll long longconst int N = 1e6 + 10, inf = 1e9;
const ll INF = 1e18;int n, k, a[N], s[N]; // si: i元素的位置
ll f[N][2]; //f:第i个数，恰好在 1/k 位置上取到的最小花费
int p[N][2]; //p:第i个数在1/k上时下一个不在1~k的数字struct seg_tree{int l, r, sum; // 维护区间 [l, r] 中的数位置在 1~k 上的数量 
}tr[N * 4];void pushup(int p){tr[p].sum = tr[ls].sum + tr[rs].sum;
}
void build(int p, int l, int r){tr[p] = {l, r, 0};if(l == r) return ;int mid = (l + r) >> 1;build(ls, l, mid); build(rs, mid + 1, r);
}void update(int p, int loc, int x){if(tr[p].l == tr[p].r) return void(tr[p].sum += x);int mid = tr[ls].r, ans = 0;if(loc <= mid) update(ls, loc, x);else update(rs, loc, x);pushup(p);
}int query(int p, int l, int r){  // 查询 [l, r] 区间第一个为0的数的位置if(tr[p].sum == tr[p].r - tr[p].l + 1) return inf;if(tr[p].l == tr[p].r) return tr[p].l;int mid = tr[ls].r, ans = inf;if(l <= mid) ans = query(ls, l, r);if(r > mid && ans == inf) ans = query(rs, l, r);return ans;
}void init(){for(int i = 1; i <= n; i ++){for(int j = 0; j < 2; j ++) f[i][j] = INF;}build(1, 1, n);int s[3] = {1, k}, l = 1, r = k; // s[0/1]:此时1/k上的元素是什么for(int i = 1; i <= k; i ++) update(1, a[i], 1); // 将1~k位置的元素设置为1，代表已经在1~k区间内了for(int i = 1; i <= n; i ++){for(int j = 0; j < 2; j ++){if(a[s[j]] == n) continue ;p[a[s[j]]][j] = query(1, a[s[j]] + 1, n);}// 那么现在在1/k上的数就是之前n/k-1上的数update(1, a[s[1]], -1); // 删除for(int j = 0; j < 2; j ++){s[j] = (s[j] - 1 + n) % n;if(!s[j]) s[j] = n;}update(1, a[s[0]], 1); // 新增}
}int get_dis(int x, int y){ // 从x -> y 需要右移的距离return (y - x + n) % n;
}
int get_min(int x, int y){ // 从x -> y 最小移动距离if(y < x) swap(x, y);return min(y - x, x + n - y);
}void solve(){cin >> n >> k;for(int i = 1; i <= n; i ++){cin >> a[i]; s[a[i]] = i;}if(k == n){cout << "0\n";return ;}init();ll ans = INF, sta = 1;while(s[sta] <= k) sta ++;f[sta][0] = get_min(s[sta], 1);f[sta][1] = get_min(s[sta], k);for(int i = sta; i < n; i ++){for(int j = 0; j < 2; j ++){if(f[i][j] == INF) continue ;if(p[i][j] > n) ans = min(ans, f[i][j]);else{int pos = s[p[i][j]] + get_dis(s[i], j==0?1:k);if(pos > n) pos -= n;// 根据数组右移的距离算出元素i此时的具体位置int d0 = get_min(pos, 1), d1 = get_min(pos, k);f[p[i][j]][0] = min(f[p[i][j]][0], f[i][j] + d0);f[p[i][j]][1] = min(f[p[i][j]][1], f[i][j] + d1);}}}ans = min({ans, f[n][0], f[n][1]});cout << ans << "\n";
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t;cin >> t;while(t --){solve();}return 0;
}

关于这样的特殊状态压缩的递推dp，还推荐一道题 2023年牛客多校第四场的链接J Qu’est-ce Que C’est?，在博主本人的博客2023牛客暑假多校第四场（补题向题解：J）中的法二就是用了状态压缩的思想。

法二（直接转移）

博主个人的写法，时空复杂度比法一的更优秀，但是却不太会证明，所以还是推荐法一。
在这里插入图片描述

思路

关于状态 $f [i] [0/ k]$ 和法一状态定义相同，博主写题解决元素 $i$ 本来就在 $1\sim k$ 位置上时曾考虑多加一维状态 $f [i] [2]$ ，代表在原地不动，但是这样却无法记录此时数组转动的情况，并且就算能记录转动的距离， $f [i - 1] [0/1]$ 可能转移出位置不同的两个 $f [i] [2]$ ，这样状态表示肯定不够于是赛时就没做出。

赛后考虑到，若是元素 $i$ 已经落在 $2\sim k-1$ 上时，用 map 记录此时的状态 $f i rs t :$ 数组右移的距离， $seco n d :$ 最小花费。遍历map的状态进行转移时，若是 $i + 1$ 已经在 $2\sim k-1$ 中就继续保留状态，若是落在 $\geq k$ 的位置上就可以转移到 $f [i] [0/1]$ ，从map中删除这一状态。 ~~凭感觉~~ 这样的状态不会很多，转移不会耗费太多时间。具体的转移方程和解法一相同，这里就不再赘述，具体见代码。

#include <bits/stdc++.h>
using namespace std;#define ll long longconst int N = 1e6 + 10; 
const ll inf = 1e18;int n, k, p[N], s[N];
ll f[N][2]; // 第i个数，恰好在 1/k 位置上取到的最小花费
map<int, ll> mp; // 存处于 1~k 中间的数的状态 右移的距离 + 花费int get_dis(int x, int y){return (y - x + n) % n;
}int get_min(int x, int y){if(y < x) swap(x, y);return min(y - x, x + n - y);
}void solve(){cin >> n >> k;for(int i = 1; i <= n; i ++){cin >> p[i]; s[p[i]] = i;}if(k == n){cout << "0\n";return ;}mp.clear();for(int i = 1; i <= n; i ++){for(int j = 0; j < 2; j ++) f[i][j] = inf;}ll ans = inf, sta = 1;while(s[sta] <= k) sta ++;f[sta][0] = get_min(s[sta], 1);f[sta][1] = get_min(s[sta], k);for(int i = sta + 1; i <= n; i ++){vector<int> tmp;for(auto it = mp.begin(); it != mp.end(); it ++){ll d = it->first, v = it->second;int pos = s[i] + d; // 根据数组右移的距离算出元素i此时的具体位置if(pos > n) pos -= n;if(pos > 1 && pos < k) continue ; // 在if(pos > k){ // 大于k就需要转移到f[i][0/1]去int d0 = get_min(pos, 1), d1 = get_min(pos, k);f[i][0] = min(f[i][0], v + d0);f[i][1] = min(f[i][1], v + d1);}   else if(pos == 1) f[i][0] = min(f[i][0], v); // 等于1/k 直接转移else if(pos == k) f[i][1] = min(f[i][1], v);tmp.push_back(it->first);// mp.erase(it);}for(auto x : tmp) mp.erase(x); // 删除转移出 1~k 的状态for(int j = 0; j < 2; j ++){if(f[i - 1][j] == inf) continue ;int dis = get_dis(s[i - 1], j==0?1:k);int pos = s[i] + dis;if(pos > n) pos -= n;if(pos > 1 && pos < k){auto it = mp.find(dis);if(it == mp.end()) mp[dis] = f[i - 1][j];else it->second = min(it->second, f[i - 1][j]);}else if(pos == 1) f[i][0] = min(f[i][0], f[i - 1][j]);else if(pos == k) f[i][1] = min(f[i][1], f[i - 1][j]);else{int d0 = get_min(pos, 1), d1 = get_min(pos, k);f[i][0] = min(f[i][0], f[i - 1][j] + d0);f[i][1] = min(f[i][1], f[i - 1][j] + d1);}}}int ans = min(f[n][0], f[n][1]);for(auto it : mp) ans = min(ans, it.second);cout << ans << "\n";
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t;cin >> t;while(t --){solve();}return 0;
}