@description@
给定一个长度为 N 的序列 A，将其划分成 K + 1 段，划分的代价为每一段中两两元素的异或之和。
求最小划分代价。
1 ≤ K < N ≤ 5000，0 ≤ Ai ≤ 10^9。
@solution@
一个朴素的 dp：定义 dp[i][j] 表示将前 j 个数划分成 i 段的最小代价。
转移时枚举 k <= j，用 dp[i-1][k-1] + cost(k, j) 转移到 dp[i][j]。
看了一会儿没什么优化的思路，那么考虑决策单调性。记 pnt[i][j] 表示 dp[i][j] 的最优决策点。
通过打表发现好像有 pnt[i][j-1] <= pnt[i][j] 与 pnt[i-1][j] <= pnt[i][j] 两重单调性存在。
感性理解起来好像两个都是对的。
前一个直接可以证，后面一个需要用平行四边形不等式的方法来分析。这里就不再详细阐述了。
因此有 pnt[i-1][j] <= pnt[i][j] <= pnt[i][j+1]，通过从小到大枚举 i，从大到小枚举 j 的方法可以求出 pnt[i][j] 的范围，直接在这个范围内暴力找最优决策点即可。
时间复杂度？求 pnt[i][j] 需要扫描 pnt[i][j+1] - pnt[i-1][j] 个数，可以写成 (pnt[i][j+1] - pnt[i][j]) + (pnt[i][j] - pnt[i-1][j])。
对于每一个 i, j，将上式进行求和，最终结果为 ∑(pnt[i][n] + pnt[n][i])。
注意到 pnt[i][n], pnt[n][i] <= n，因此时间复杂度为 O(n^2)。
@accepted code@
#include <cstdio>
typedef long long ll;
const int MAXN = 5000;
const ll INF = (1LL<<60);
ll f[MAXN + 5], g[MAXN + 5];
int pnt[MAXN + 5], tmp[MAXN + 5];
ll c[MAXN + 5][MAXN + 5];
int A[MAXN + 5];
int main() {
int N, K; scanf("%d%d", &N, &K), K++;
for(int i=1;i<=N;i++) scanf("%d", &A[i]);
for(int i=1;i<=N;i++) {
ll s = 0;
for(int j=i-1;j>=1;j--) {
s += (A[i] ^ A[j]);
c[j][i] = c[j][i-1] + s;
}
}
for(int i=1;i<=N;i++) f[i] = INF, pnt[i] = 1;
for(int i=1;i<=K;i++) {
for(int j=1;j<=N;j++) g[j] = f[j], f[j] = INF, tmp[j] = pnt[j];
for(int j=N;j>=i;j--) {
int l = tmp[j], r = (j == N ? N : pnt[j+1]), m = l;
for(int k=l;k<=r&&k<=j;k++)
if( f[j] > g[k-1] + c[k][j] )
f[j] = g[k-1] + c[k][j], m = k;
pnt[j] = m;
}
}
printf("%lld
", f[N]);
}
@details@
其实不详细阐述的原因是我自己还没有看懂平行四边形不等式优化。