[CF868-F] Yet Another Minimization Problem
时间限制:1000MS 内存限制:262144KB
难度:\(6.0\)
-
题目描述
有 \(n\) 个正整数构成序列 \(a\) ,定义一个区间 \([l, r]\) 的代价为 满足 \(l \leq i, j \leq r\) 并使得 \(a_i=a_j\) 的无序对 \([i, j]\) 的数量。
现要把 \(a\) 分成 \(k\) 个互不相交且不为空的连续的区间,求出在所有分法中,分出区间的最小代价和是多少。
-
输入格式
第一行,两个正整数 \(n, k\) 。
第二行,序列 \(a\) ,共 \(n\) 个元素,用一个空格隔开。
-
输出格式
一个整数,表示在所有分法中,分出区间的最小代价和。
-
样例输入
1 2 |
7 3 1 1 3 3 3 2 1 |
-
样例输出
1 |
1 |
-
样例说明
一种可能的分法为 \([1], [1, 3], [3, 3, 2, 1]\) 。
第一个区间的代价为 \(0\) ,第二个区间的代价为 \(0\) ,第三个区间的代价为 \(1\) ,最小代价和为 \(1\) 。
(其他样例见原题
-
数据范围
对于 \(10\%\) 的数据,\(2 \leq n \leq 20\) 。
对于 \(40\%\) 的数据,\(2 \leq n \leq 1000\) 。
对于 \(100\%\) 的数据,\(2 \leq n \leq 10^5\) ,\(2 \leq k \leq min\{20,n\}\) 。
保证 \(1 \leq a_i \leq n\) 。
\(Source\): CF868-F
设 \(f_{i, j}\) 为做到第 \(i\) 个数,\(1\) ~ \(i\) 中分了 \(j\) 段的最小代价。
所以 \(f_{i,j}=\min\limits_{k=1}^{i-1}\{f_{k,j-1}+w_{k,i}\}\) , \(w_{k, i}\) 表示 \([k+1, i]\) (注意范围) 为一段的代价(两两相同的数的无序对对数),发现 \(j\) 这一维可以直接滚动掉(不滚动其实也没什么www)。
就变成了 \(g_i=\min\limits_{k=1}^{i-1}\{f_k+w_{k,i}\}\) ,时间复杂度 \(O(n^2k)\) 无法通过本题。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define _min(_a,_b) ((_a)<(_b)?(_a):(_b)) inline int getnum() { register char c=getchar(); while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') { a*=10;a+=c-'0'; c=getchar(); } return a; } int a[105050],cnt[105050],xf; long long f[2][105050],w; #define _add(_a) (w+=cnt[_a]++) #define _del(_a) (w-=--cnt[_a]) int main() { register int N=getnum(),K=getnum(); for(register int i=1;i<=N;i++) a[i]=getnum(); w=0; for(register int i=1;i<=N;i++) f[0][i]=_add(a[i]); memset(cnt,0,sizeof(cnt));w=0; for(register int j=2;j<=K;j++) { xf^=1; memset(&f[xf],0x3F,sizeof(f[xf])); for(register int i=1;i<=N;i++) { for(register int k=1;k<=i;k++) _add(a[k]); for(register int k=1;k<i;k++) _del(a[k]),f[xf][i]=_min(f[xf][i],f[xf^1][k]+w); _del(a[i]); } } printf("%lld\n",f[xf][N]); return 0; } |
(注:记一段区间内相同的数的无序对对数可以方便地开一个桶,增加一个元素 \(a\) 表示 w+=cnt[a]++;
,删除一个元素 \(a\) 表示 w-=--cnt[a];
,因为相同元素 \(a\) 的无序对对数为 \(C_{cnt_a}^2=\frac{cnt_a(cnt_a-1)}{2} = 1+2+\cdots+(cnt_a-1)\) 。
(要求 \(w_{k, i}\) ,只需要把 \(1\) ~ \(i\) 的所有元素先加到一个变量 \(w\) 中,然后依次删除 \(1, 2, \cdots , i\) ,删除第 \(k\) 个元素后 \(w\) 的值就为 \(w_{k, i}\) 。
继续优化,同时注意到决策的单调性。即对于 \(a<b<c<d\),如果 \(c\) 从 \(b\) 转移过来比从 \(a\) 转移过来更优,那么 \(d\) 从 \(b\) 转移过来也比从 \(a\) 转移过来更优。即若满足 \({{f_b} + {w_{b,c}} \le {f_a} + {w_{a,c}}}\) 那么一定满足 \({{f_b} + {w_{b,d}} \le {f_a} + {w_{a,d}}}\) 。注意到只要满足 \(w_{b,d}-w_{b,c} \leq w_{a,d}-w_{a,c}\) 那么上面的结论一定成立。发现这个条件其实就是四边形不等式 \(w_{a,c}+w_{b,d} \leq w_{a,d}+w_{b,c}\) 。
对于本题,假设颜色 \(a\) 分别在 \((a,b]\) 、 \((b,c]\) 、 \((c,d]\) 中的数量为 \(x ,y, z\) 。那么就有如下关系(倒推):
\(\begin{array}{c} {w_{a,c}} + {w_{b,d}} \le {w_{a,d}} + {w_{b,c}}\\ C_{x + y}^2 + C_{y + z}^2 \le C_{x + y + z}^2 + C_y^2\\ \left( {x + y} \right)\left( {x + y – 1} \right) + \left( {y + z} \right)\left( {y + z – 1} \right) \le \left( {x + y + z} \right)\left( {x + y + z – 1} \right) + \left( {y + z} \right)\left( {y + z – 1} \right)\\ 0 \le xz \end{array}\)
\(0 \leq xz\) 那是废话一定正确,也就证明了决策的单调性。
同时还发现此题的 \(w_{k,i}\) 无法对于指定的 \(k, i\) 在 \(O(1)\) 时间内求出,所以无法使用决策二分栈等方法,考虑操作是单调并且离线,所以使用分治。
求解区间:\(|\gets\) 之前处理的信息 \(\to|\) \(l\frac{\qquad\qquad\qquad\downarrow^{mid}\qquad\qquad\qquad}{}r\)
决策区间:\(kl\frac{\qquad\qquad\qquad\qquad\qquad\qquad\downarrow^{k}\qquad\qquad\qquad}{}kr\)
这里之前处理的信息主要指 \(w\) 和 \(cnt\) 数组。
当前求解的区间为 \([l, r]\) ,而最优决策可能在的区间为 \([kl, kr]\) 。则对于 \(mid=\lfloor\frac{l+r}{2}\rfloor\) ,需要暴力找出 \([kl, min\{mid-1, kr\}]\) 中最优的转移点 \(k\) 。
注意,之前预处理的信息 \(w\) 表示 \([kl, l)\) 这一区间的代价,所以在寻找最优转移点的时候按照朴素DP的方法快速计算出所需的 \(w\) 。记得算完后要复原。
要处理 \([l, mid)\) 时,它的决策区间为 \([kl, k]\) 。因为 \(w\) 原本就表示 \([kl, l]\) 这一区间的代价,所以不需要加任何处理即可直接递归进这个子区间。
值得注意的是,处理 \((mid, r]\) 时,它的决策区间为 \([k, kr]\) 。对照上面的简图发现有 \([l, k)\) 这一段信息还未处理,所以先处理出它的信息,然后就可以递归进这个子区间了。记得回溯的时候复原。
这样分治的优秀复杂度 \(O(nklogn)\) 就可以通过本题了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define _min(_a,_b) ((_a)<(_b)?(_a):(_b)) inline int getnum() { register char c=getchar(); while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') { a*=10;a+=c-'0'; c=getchar(); } return a; } int a[105050],cnt[105050],xf; long long f[2][105050],w; #define _add(_a) (w+=cnt[_a]++) #define _del(_a) (w-=--cnt[_a]) void Divide(register int l,register int r,register int kl,register int kr) { if(l>r) return; register int mid=(l+r)>>1,krr=_min(mid-1,kr); for(register int i=l;i<=mid;i++) _add(a[i]); register int k=kl; for(register int i=kl;i<=krr;i++) { _del(a[i]); if(f[xf][mid]>f[xf^1][i]+w) { f[xf][mid]=f[xf^1][i]+w; k=i; } } for(register int i=kl;i<=krr;i++) _add(a[i]); for(register int i=l;i<=mid;i++) _del(a[i]); Divide(l,mid-1,kl,k); for(register int i=l;i<=mid;i++) _add(a[i]); for(register int i=kl;i<k;i++) _del(a[i]); Divide(mid+1,r,k,kr); for(register int i=kl;i<k;i++) _add(a[i]); for(register int i=l;i<=mid;i++) _del(a[i]); } int main() { register int N=getnum(),K=getnum(); for(register int i=1;i<=N;i++) a[i]=getnum(); w=0; for(register int i=1;i<=N;i++) f[0][i]=_add(a[i]); memset(cnt,0,sizeof(cnt));w=0; for(register int j=2;j<=K;j++) { xf^=1; memset(&f[xf],0x3F,sizeof(f[xf])); /*for(register int i=1;i<=N;i++) { for(register int k=1;k<=i;k++) _add(a[k]); for(register int k=1;k<i;k++) _del(a[k]),f[xf][i]=_min(f[xf][i],f[xf^1][k]+w); _del(a[i]); }*/ Divide(1,N,1,N); } printf("%lld\n",f[xf][N]); return 0; } |