dp，方程很好想，我们设$f_{i, j}$,表示前j个数字划分成i个区间的最大价值， 设$g_{l, r}$表示[l, r]这个区间中颜色的数量，有转移：
$f_{i, j} = max(f_{i - 1, k} + g_{k + 1, i})$
$(0\leq k < j) $
用一个数据结构优化g的计算， 这个式子是O(kn^2logn)的。
考虑到对于每一个i，其g的取值区间是从左向右不断缩小的，而右端点是不变的，每一段颜色对g的贡献是从[前一个出现的位置+1, 现在的位置] , 所以我们可以用一棵线段树来储存上一层i的f值，对每一个颜色块计算贡献。因为转移中存在下标0，所以把f的值全部右移一位，时间复杂度$O(knlogn)$
Code:
#include <cstdio>using namespace std;const int N = 35005;const int M = 55;int n, m, a[N], pre[N], last[N], f[M][N];inline void read(int &X) {X = 0;char ch = 0;int op = 1;for(; ch > '9'|| ch < '0'; ch = getchar())if(ch == '-') op = -1;for(; ch >= '0' && ch <= '9'; ch = getchar())X = (X << 3) + (X << 1) + ch - 48;X *= op;}inline int max(int x, int y) {return x > y ? x : y;}namespace SegT {int s[N << 2], tag[N << 2];#define lc p << 1#define rc p << 1 | 1#define mid ((l + r) >> 1)inline void up(int p) {if(p) s[p] = max(s[lc], s[rc]);}inline void down(int p) {if(!tag[p]) return;s[lc] += tag[p], s[rc] += tag[p];tag[lc] += tag[p], tag[rc] += tag[p];tag[p] = 0;}void build(int p, int l, int r, int pos) {tag[p] = 0;if(l == r) {s[p] = f[pos][l - 1];return;}build(lc, l, mid, pos);build(rc, mid + 1, r, pos);up(p);}void modify(int p, int l, int r, int x, int y, int v) {if(x <= l && y >= r) {tag[p] += v, s[p] += v;return;}down(p);if(x <= mid) modify(lc, l, mid, x, y, v);if(y > mid) modify(rc, mid + 1, r, x, y, v);up(p);}int query(int p, int l, int r, int x, int y) {if(x <= l && y >= r) return s[p];down(p);int res = 0;if(x <= mid) res = max(res, query(lc, l, mid, x, y));if(y > mid) res = max(res, query(rc, mid + 1, r, x, y));return res;}} using namespace SegT;int main() {read(n), read(m);for(int i = 1; i <= n; i++) {read(a[i]);pre[i] = last[a[i]];last[a[i]] = i;}/* for(int i = 1; i <= n; i++)printf("%d ", pre[i]);printf("\n"); */for(int i = 1; i <= m; i++) {build(1, 1, n, i - 1);for(int j = 1; j <= n; j++) {modify(1, 1, n, pre[j] + 1, j, 1);f[i][j] = query(1, 1, n, 1, j);}}printf("%d\n", f[m][n]);return 0;}
最近写了好多线段树
