因为输入法没有给我满意的候选项所以这次就不取抽象标题了。
可恶每道题还要证明一下满足四边形不等式，真是难为我了。
A - Chef and Bitwise OR Operation
https://vjudge.net/contest/602275#problem/A
CodeChef - CHEFAOR。
看到「刚好 \(K\) 个」，脑子一热差点去写 wqs（
实际上当然是不需要的。观察数据范围，至少 \(n^2\) 跑得过。令 \(f_{i, j}\) 表示将前 \(i\) 个分为 \(j\) 段的最小代价。预处理一个 \(s_{l,r}\) 表示 \([l,r]\) 按位或起来的值，用一个类前缀和就可以 \(\mathcal O(n^2)\)。那么有：
\[f_{i,j}=\min\{f_{k,j-1}+s_{k+1,j}\}
\]
然后对于代价函数 \(w=s\)，四边形不等式成立。不是很想写，但是还是写一下吧。
就，最好还是把线段图画出来，其实挺显然的。
假设 \(x=w(b,d),y=w(a,d)-w(b,d),z=w(a,c)-y\)，有 \(w(a,c)=y+z,w(a,c)+w(b,d)=x+y+z\)，这是交叉。
那么 \(w(b,c)\ge z,w(a,d)=x+y\)，有 \(w(a,d)+w(b,c)\ge x+y+z\)，这是包含。交叉小于包含，四边形不等式成立。
那么就可以直接写了。复杂度 \(\mathcal O(T\times n^2)\)。