题目链接：http://codeforces.com/contest/834/problem/D
题意：
把n个数分成k段，每段的价值等于这一段内不同数字的个数，求总的最大价值。
可以很快发现这是一个dp，dp[i][j]表示到第i个数字，已经分成了k段的最大价值
dp[i][j] = max(dp[t][j-1]) (1<= t < i)
对于状态i，j，线段树维护的是1~i-1的最大值
对于每一个位置，找到前面最后一个与它数字相同的的位置，把这之间线段树的值都加上1，然后dp[i][j]的值就是j-1到i-1的最大值。
最后答案就是dp[n][k]。
这里的DP比较特殊，循环K轮，可以省掉1维。
#include <bits/stdc++.h> using namespace std; const int maxn = 35010; int n,k,a[maxn],last[maxn],pre[maxn],dp[maxn]; struct node{ int l,r,mx,add; }tree[maxn<<2]; void pushup(int rt){ tree[rt].mx = max(tree[rt<<1].mx, tree[rt<<1|1].mx); } void pushdown(int rt){ if(tree[rt].add){ tree[rt<<1].add += tree[rt].add; tree[rt<<1|1].add += tree[rt].add; tree[rt<<1].mx += tree[rt].add; tree[rt<<1|1].mx += tree[rt].add; tree[rt].add = 0; } } void build(int l, int r, int rt){ tree[rt].l = l, tree[rt].r = r, tree[rt].add = 0; if(l == r){ tree[rt].mx = dp[l]; return; } int mid = (l+r)>>1; build(l, mid, rt<<1); build(mid+1, r, rt<<1|1); pushup(rt); } void update(int L, int R, int val, int rt){ if(L<=tree[rt].l&&tree[rt].r<=R){ tree[rt].add += val; tree[rt].mx += val; return; } pushdown(rt); int mid = (tree[rt].l+tree[rt].r)>>1; if(R<=mid) update(L,R,val,rt<<1); else if(L>mid) update(L,R,val,rt<<1|1); else{ update(L,mid,val,rt<<1); update(mid+1,R,val,rt<<1|1); } pushup(rt); } int query(int L, int R, int rt){ if(L<=tree[rt].l&&tree[rt].r<=R){ return tree[rt].mx; } pushdown(rt); int mid=(tree[rt].l+tree[rt].r)>>1; if(R<=mid) return query(L,R,rt<<1); else if(L>mid) return query(L,R,rt<<1|1); else return max(query(L,mid,rt<<1),query(mid+1,R,rt<<1|1)); } int main() { scanf("%d %d", &n,&k); for(int i=1; i<=n; i++){ scanf("%d", &a[i]); pre[i] = last[a[i]]; last[a[i]] = i; } for(int j=1; j<=k; j++){ build(0, n, 1); for(int i=j; i<=n; i++){ update(pre[i],i-1, 1, 1); dp[i] = query(j-1, i-1, 1); } } printf("%d\n", dp[n]); return 0; }
