题意
将长度为 \(n\) 的序列分为恰好 \(k\) 段，每段的权值和定义为出现的 \(a[i]\) 的种类，请最大化每一段的权值总和。
朴素dp
记 \(f[i][j]\) 表示 \(1 \sim i\)，被分成 \(j\) 段，最大权值和。有转移：
\[f[i][j] = \max_{1\le k \lt i} f[k][j - 1] + val(k + 1, i) \]dp时优化区间枚举有一个常用技巧：类似双指针地去不断扩展区间，避免多次计算同一个区间的贡献。
本题就是倒着枚举 \(k\)，每加一个数就更新 \(val\)。
int f[N][50], a[N], t[N];
int n, m;
int add(int x){
if(!t[x]) {
t[x] = 1;
return 1;
}
return 0;
}
signed main(){
n = rd(), m = rd() - 1;
F(i, 1, n) a[i] = rd();
F(j, 0, m){
F(i, 1, n){
F(i, 1, n) t[i] = 0;
int val = add(a[i]);
G(k, i - 1, 0){
if(j) f[i][j] = max(f[k][j - 1] + val, f[i][j]);
else f[i][j] = val;
if(k) val += add(a[k]);
}
}
}
printf("%d", f[n][m]);
return fflush(0), fclose(stdin), fclose(stdout), 0;
}
线段树优化
固定 \(j\)，考虑如何从 \(f[i][j - 1]\) 转移到 \(f[i + 1][j]\)。
发现较难处理的是 \(a[i + 1]\) 对 \(val(?,i + 1)\) 的影响。这里使用到一个小trick。
记 \(pre[a[i]]\) 表示 \(a[i]\) 上一次出现的位置。对于位置 \(j\)，
若 \(j \ge pre[a[i + 1]]\) ，\(val(j + 1, i + 1) + 1\)。
若 \(j \lt pre[a[i + 1]]\)，\(val(j + 1, i + 1)\) 不变。
如上，在线段树上区间加，区间查就可以了。
时间复杂度 \(O(Tn\log n)\)。
（所以单独写了个单点加，为什么更慢？）
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
using namespace std;
using ll = long long;
char buf[100], *p1 = buf, *p2 = buf;
inline int gc(){ return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100,stdin),p1==p2)?EOF:*p1++; }
inline int rd(){
int x = 0; char ch;
while(!isdigit(ch = gc()));
do x = (x << 3) + (x << 1) + (ch ^ 48); while(isdigit(ch = gc()));
return x;
}
const int N = 35500;
int pre[N], nw[N], a[N], f[N][50];
int n, m;
struct Segtree{
int mx[N << 2], tag[N << 2];
void pushup(int u){
mx[u] = max(mx[u * 2], mx[u * 2 + 1]);
}
void push(int u, int v){
mx[u] += v;
tag[u] += v;
}
void pushdown(int u){
if(tag[u]){
push(u * 2, tag[u]);
push(u * 2 + 1, tag[u]);
tag[u] = 0;
}
}
void update(int u,int l, int r, int x, int y, int v){
if(l >= x && r <= y){
push(u, v);
return ;
} pushdown(u);
int mid = (l + r) >> 1;
if(x <= mid) update(u * 2, l, mid, x, y, v);
if(y > mid) update(u * 2 + 1, mid + 1, r, x, y, v);
pushup(u);
}
void change(int u, int l, int r, int x, int v){
if(l == r){
mx[u] += v;
return ;
} pushdown(u);
int mid = (l + r) >> 1;
if(x <= mid) change(u * 2, l, mid, x, v);
else change(u * 2 + 1, mid + 1, r, x, v);
pushup(u);
}
int query(int u, int l, int r, int x, int y){
if(l >= x && r <= y) return mx[u];
pushdown(u);
int mid = (l + r) >> 1, ret = 0;
if(x <= mid) ret = max(ret, query(u * 2, l, mid, x, y));
if(y > mid) ret = max(ret, query(u * 2 + 1, mid + 1, r, x, y));
return ret;
}
}tr[50];
signed main(){
n = rd(), m = rd() - 1;
F(i, 1, n) a[i] = rd();
F(i, 1, n){
pre[a[i]] = nw[a[i]], nw[a[i]] = i;
F(j, 0, min(m, i - 1)) tr[j].update(1, 0, n, pre[a[i]], i - 1, 1);
F(j, 0, min(m, i - 1)){
if(!j){
f[i][j] = f[i - 1][j] + (!pre[a[i]]); // a[i] 第一次出现, 则有贡献
}
else{
f[i][j] = tr[j - 1].query(1, 0, n, j - 1, i - 1);
}
tr[j].change(1, 0, n, i, f[i][j]);
}
}
printf("%d", f[n][m]);
return fflush(0), fclose(stdin), fclose(stdout), 0;
}