我觉得我要改一下签名了……怎么会有窝这么啰嗦的人呢？
做这题需要先学习左偏树《左偏树的特点及其应用》 然后做一下POJ3666，这题的简单版。
思路：
考虑一下维护中位数的过程
原数组为A，找到的不降数列为B
当对于A的前n个数已经找好了最优解B[1…n]，可知此时A被分成很多块，并被一些大顶堆记录，假设第i块有num个数，那么第i个堆维护这一块的最小的(num+1)/2个数，堆顶即为中位数。
假设已经处理好前7个数，被分为两块 ([a,b],c,d) ([h,e],f) （每一块按升序排列，[]中的数是堆里面维护的。
因为数列是不降的，所以b≤e
当新添加一个元素的时候，设为x，如果x≤e，将需要向前合并。
那么新的块应该是……分两种情况……
1.x>h ([h,x],e,f)
2.x<h ([x,h],e,f)
设新的中位数是val＝max(h, x) 分类讨论一下可以发现改变的值是(e-val)+(val-x)
这里假设是([x,h],e,f)
当h<b时，需要继续向前合并。
合并之后是([x,h,a,b],c,d,e,f) (顺序已经不确定了，只能确定栈中元素和栈顶是b
可以发现大小为偶数的块和偶数的块合并，合并后的堆不需要弹出元素。
合并前([a,b],c,d) 的中位数是b ([x,h],e,f)的中位数是h， 合并后的中位数的b
可知答案改变都是发生在集合([x,h],e,f)中的，我们又知道b≤e（上面提到过），那么很容易得到答案是不变哒！（就是把(h-x)+(h-h)+(e-h)+(f-h)变成了(b-x)+(b-h)+(e-b)+(f-b)，值是一样的
上面是偶数和偶数合并，继续讨论前一块奇数和后一块偶数合并。
设前一块是([a,b],c) 中位数是b，后一块是([d,e],f,g)中位数是e，合并后不需要弹出，中位数是b，类似上面的情况，我们可以得出b≤f，所以答案仍然不变。
前一块偶数，后一块奇数
([a,b],c,d)中位数是b ([e,f],g)中位数是f 合并后不需要弹出 中位数是b 其中(f<b≤g)
那么答案由([e,f],g)的改变产生，f的左右两边是可以抵消掉的，改变只会因为f，改变的值是b-f
前一块奇数，后一块奇数
设前一块是([a,b],c) 中位数是b，后一块是([d,e],f,)中位数是e 其中e<b≤f
合并后弹出元素b，中位数为max(a,e)，设为val
那么答案改变就是b-e
到此，所有情况都讨论完了ˊ_>ˋ
结论：当一个块和前面的块合并时，如果当前块的数量为偶数，答案不变，否则答案增加（前一块的中位数－当前块的中位数）
代码：
/***************************************** Problem: 3016 User: G_lory Memory: 12676K Time: 1797MS Language: G++ Result: Accepted *****************************************/ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 2005; const int INF = 0x5f5f5f5f; typedef long long ll; struct LTree { int l, r, sz; int key, dis; bool operator<(const LTree lt) const { return key < lt.key; } } tr[N]; int cnt_tr; int NewTree(int k) { tr[++cnt_tr].key = k; tr[cnt_tr].l = tr[cnt_tr].r = tr[cnt_tr].dis = 0; tr[cnt_tr].sz = 1; return cnt_tr; } int Merge(int x, int y) { if (!x || !y) return x + y; if (tr[x] < tr[y]) swap(x, y); tr[x].r = Merge(tr[x].r, y); if (tr[tr[x].l].dis < tr[tr[x].r].dis) swap(tr[x].l, tr[x].r); tr[x].dis = tr[tr[x].r].dis + 1; tr[x].sz = tr[tr[x].l].sz + tr[tr[x].r].sz + 1; return x; } int Top(int x) { return tr[x].key; } void Pop(int &x) { x = Merge(tr[x].l, tr[x].r); } int root[N], num[N]; void cal(int a[], int n, int ans[]) { int res; cnt_tr = res = 0; int cnt = 0; for (int i = 0; i < n; ++i) { root[++cnt] = NewTree(a[i]); num[cnt] = 1; while (cnt > 1 && Top(root[cnt]) < Top(root[cnt-1])) { cnt--; if (num[cnt+1]&1) res += Top(root[cnt]) - Top(root[cnt+1]); root[cnt] = Merge(root[cnt], root[cnt+1]); num[cnt] += num[cnt+1]; while (tr[root[cnt]].sz*2 > num[cnt]+1) { Pop(root[cnt]); } int now = Top(root[cnt]); } ans[i] = res; } } int a[N], b[N], c[N]; int in[N][N], de[N][N]; int dp[N][N]; int main() { //freopen("in", "r", stdin); int n, k; while (~scanf("%d%d",&n, &k) && n) { for (int i = 1; i <= n; ++i) { scanf("%d", a+i); b[i] = a[i]-i; c[i] = -a[i]-i; } for (int i = 1; i <= n; ++i) { cal(c+i, n-i+1, de[i]+i); cal(b+i, n-i+1, in[i]+i); } for (int i = 1; i <= n; ++i) dp[0][i] = INF; for (int i = 1; i <= k; ++i) { dp[i][0] = 0; for (int j = 1; j <= n; ++j) { dp[i][j] = INF; for (int p = 0; p < j; ++p) { dp[i][j] = min(dp[i][j], dp[i-1][p] + min(in[p+1][j], de[p+1][j])); } } } printf("%d ", dp[k][n]); } return 0; }