D. The Bakery
题目链接
分类：data structures dp
1.题意概述
把n个数分成k段，每段的价值等于这一段内不同数字的个数，求总的最大价值。
2.解题思路
可以考虑动态规划，
dp[i][j]
表示到第
i
个数字已经分成
j段的最大值，那么容易得到转移方程为
dp[i][j]=max(dp[k][j−1]),1≤k≤i−1
，但是如果我们去枚举
i,j,k
复杂度是
O(n3)
的，考虑到
1 ≤ n ≤ 35000
，这样的复杂度是不能接受的，我们考虑优化最大值的转移，原先为
O(n)
我们可以考虑用线段树去维护当前位置前面的最大值（也就是对于状态
dp[i][j]
，线段树去维护
dp[k][j−1],1≤k≤i−1
的最大值），对于每个位置的更新：找到前面最后一个与它数字相同的位置，然后把这之间的线段树权值都+1，最后查询时候从树中查询转移就是每次的答案，这样每次查询和更新都是
O(logn)
的，最终答案就是
dp[n][k]
！时间复杂度：
O(nklogn)
3.AC代码
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-6
#define e exp(1.0)
#define pi acos(-1.0)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)(x).size())
#define All(x) (x).begin(),(x).end()
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define Close() ios::sync_with_stdio(0),cin.tie(0)
#define INF 0x3f3f3f3f
#define maxn 35010
#define N 1111
typedef vector<int> VI;
typedef pair<
int,
int> PII;
typedef long long ll;
typedef unsigned long long ull;
const int mod =
1e9 +
7;
int dp[maxn];
class SegmentTree {
public:
#define lson root << 1
#define rson root << 1 | 1
#define lent (t[root].r - t[root].l + 1)
#define lenl (t[lson].r - t[lson].l + 1)
#define lenr (t[rson].r - t[rson].l + 1)
struct Tree {
int l, r, val, lazy;
} t[maxn <<
4];
void pushup(
int root) {
t[root].val = max(t[lson].val, t[rson].val);
}
void pushdown(
int root) {
if (t[root].lazy) {
t[lson].lazy += t[root].lazy;
t[rson].lazy += t[root].lazy;
t[lson].val += t[root].lazy;
t[rson].val += t[root].lazy;
t[root].lazy =
0;
}
}
void build(
int l,
int r,
int root) {
t[root].l = l;
t[root].r = r;
t[root].lazy =
0;
if (l == r) {
t[root].val = dp[l];
return;
}
int mid = l + r >>
1;
build(l, mid, lson);
build(mid +
1, r, rson);
pushup(root);
}
void update(
int l,
int r,
int val,
int root) {
if (l <= t[root].l && t[root].r <= r) {
t[root].val += val;
t[root].lazy += val;
return;
}
pushdown(root);
int mid = t[root].l + t[root].r >>
1;
if (l <= mid) update(l, r, val, lson);
if (r > mid) update(l, r, val, rson);
pushup(root);
}
int query(
int l,
int r,
int root) {
if (l <= t[root].l && t[root].r <= r)
return t[root].val;
pushdown(root);
int mid = t[root].l + t[root].r >>
1;
int ans = -INF;
if (l <= mid) ans = max(ans, query(l, r, lson));
if (r > mid) ans = max(ans, query(l, r, rson));
return ans;
}
#undef lenr
#undef lenl
#undef lent
#undef rson
#undef lson
} T;
int pre[maxn], last[maxn], a[maxn];
int main() {
#ifndef ONLINE_JUDGE
freopen(
"in.txt",
"r", stdin);
freopen(
"out.txt",
"w", stdout);
long _begin_time = clock();
#endif
int n, k;
scanf(
"%d%d", &n, &k);
memset(last, -
1,
sizeof last);
int cnt =
0;
rep(i,
1, n +
1) {
scanf(
"%d", &a[i]);
pre[i] = last[a[i]];
last[a[i]] = i;
if (pre[i] == -
1) cnt++;
dp[i] = cnt;
}
rep(i,
2, k +
1) {
rep(j,
1, i -
1) dp[j] = -INF;
T.build(
1, n,
1);
rep(j, i, n +
1) {
int l = max(
1, pre[j]), r = j -
1;
T.update(l, r,
1,
1);
dp[j] = T.query(
1, j -
1,
1);
}
}
printf(
"%d\n", dp[n]);
#ifndef ONLINE_JUDGE
long _end_time = clock();
printf(
"time = %ld ms.", _end_time - _begin_time);
#endif
return 0;
}
