江苏省建设网站首页,做网站的一个专题,网站制作群系统,网站次年续费题意
传送门 AtCoder ABC 328G Cut and Reorder
题解
假设答案对应的 a a a 下标 0 , 1 , ⋯ , n − 1 0,1,\cdots,n - 1 0,1,⋯,n−1 经过操作 1 变换为排列 p 0 , p 1 , ⋯ , p n − 1 p_{0},p_{1},\cdots,p_{n-1} p0,p1,⋯,pn−1#xff0c;则对于满足 p i −…题意
传送门 AtCoder ABC 328G Cut and Reorder
题解
假设答案对应的 a a a 下标 0 , 1 , ⋯ , n − 1 0,1,\cdots,n - 1 0,1,⋯,n−1 经过操作 1 变换为排列 p 0 , p 1 , ⋯ , p n − 1 p_{0},p_{1},\cdots,p_{n-1} p0,p1,⋯,pn−1则对于满足 p i − 1 ≠ p i , 0 i p_{i-1}\neq p_{i},0i pi−1pi,0i 的位置都至少要分割一次且仅需这样的分割就可以得到 a p 0 , a p 1 , ⋯ , a p n − 1 a_{p_{0}},a_{p_{1}},\cdots,a_{p_{n-1}} ap0,ap1,⋯,apn−1。则状态压缩优化 p p p 的枚举即可。
不考虑分割贡献则需要维护两个变量集合 A { a p 0 , a p 1 , ⋯ , a p m } \mathcal{A}\{a_{p_{0}}, a_{p_{1}}, \cdots,a_{p_{m}}\} A{ap0,ap1,⋯,apm}以及集合匹配的 b b b 的前缀的长度 m m m。实际上只需要维护前者因为 ∣ A ∣ m \lvert\mathcal{A}\rvert m ∣A∣m。
容易想到两类计算分割贡献的方案。一类是新增状态 a p i − 1 a_{p_{i-1}} api−1转移时可以直接判断 a p i − 1 ≠ a p i a_{p_{i-1}}\neq a_{p_{i}} api−1api时间复杂度 O ( n 2 log n ) O(n^2\log n) O(n2logn)。另一种方案是枚举分割的段此时每一个连续的段除了起始段操作 1 贡献是 c c c A \mathcal{A} A 状态数为 2 n 2^n 2n对于每一个状态可能的段规模为 O ( n 2 ) O(n^2) O(n2)时间复杂度也是 O ( n 2 log n ) O(n^2\log n) O(n2logn)实际上这是一个宽松的界对于每一个段的长度 k k k实际上对应的状态数为 2 n − k 2^{n-k} 2n−k则一个更紧的界为 O ( ∑ k 2 n − k ) O ( n log n ) O(\sum k2^{n-k})O(n\log n) O(∑k2n−k)O(nlogn)。
#include bits/stdc.h
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin n;long long c;cin c;vectorlong long a(n), b(n);for (int i 0; i n; i) {cin a[i];}for (int i 0; i n; i) {cin b[i];}auto get_min [](long long x, long long y) {x min(x, y);};const long long inf 1e18;vectorlong long dp(1 n, inf);dp[0] 0;for (int i 0; i 1 n; i) {int bi __builtin_popcount(i);for (int l 0, r 0; l n; l r) {if (i l 1) {r l 1;continue;}while (r n (~i r 1)) {r 1;}for (int ai l; ai r; ai) {int st 0;long long add 0;for (int d 1; ai d r; d) {st | 1 (ai d - 1);add abs(a[ai d - 1] - b[bi d - 1]);long long split bi 0 ? 0 : c;get_min(dp[i | st], dp[i] add split);}}}}cout dp[(1 n) - 1] \n;return 0;
}
