dp，方程很好想，我们设$f_{i, j}$ ,表示前j个数字划分成i个区间的最大价值， 设$g_{l, r}$表示[l, r]这个区间中颜色的数量，有转移：
$f_{i, j} = max(f_{i - 1, k} + g_{k + 1, i})$
$(0leq 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(" "); */ 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 ", f[m][n]); return 0; }
最近写了好多线段树