Description

給一個長度為 \(n(n\le35000)\) 的序列，值域是 \([1,n]\) ，將它分成 \(k(k\le min(n,50))\) 段，求最大得分。定義每段的得分為這段的不同數(shù)個數(shù)。

Solution

令 \(dp[i][j]?\) 表示前 \(i?\) 個數(shù)分成 \(j?\) 段的最大得分， \(num[i][j]?\) 為 \([i,j]?\) 中不同數(shù)個數(shù)。顯然有 \(dp[i][j] = max\{dp[t][j-1]+num[t+1][i]\}?\) 。每當(dāng)我們加入一個數(shù) \(a[i]?\) ，則只有 \(num[pre[i]+1][i]?\) 到 \(num[i][i]?\) 會被加 \(1?\) 。于是用線段樹維護(hù) \(dp[j][t]+cnt[j + 1][t]?\) 即可。每次重新建樹。

#include<bits/stdc++.h> using namespace std;template <class T> inline void read(T &x) {x = 0; static char ch = getchar(); for (; ch < '0' || ch > '9'; ch = getchar());for (; ch >= '0' && ch <= '9'; ch = getchar()) (x *= 10) += ch - '0'; }#define N 35001 #define rep(i, a, b) for (int i = a; i <= b; i++) #define ll long longint n, K, a[N], pos[N], pre[N], dp[N], Max[N << 2], tag[N << 2];#define ls rt << 1 #define rs ls | 1 #define mid (l + r >> 1) #define pushUp Max[rt] = max(Max[ls], Max[rs]) void build(int rt, int l, int r) {tag[rt] = 0;if (l == r) { Max[rt] = dp[l]; return; }build(ls, l, mid), build(rs, mid + 1, r);pushUp; }inline void pushDown(int rt) {int& t = tag[rt];if (t) Max[ls] += t, Max[rs] += t, tag[ls] += t, tag[rs] += t, t = 0; }void update(int rt, int l, int r, int L, int R) {if (L <= l && r <= R) { Max[rt]++, tag[rt]++; return; }pushDown(rt);if (L <= mid) update(ls, l, mid, L, R);if (R > mid) update(rs, mid + 1, r, L, R);pushUp; }int query(int rt, int l, int r, int L, int R) {if (L <= l && r <= R) return Max[rt];pushDown(rt); int ans = 0;if (L <= mid) ans = max(ans, query(ls, l, mid, L, R));if (R > mid) ans = max(ans, query(rs, mid + 1, r, L, R));return ans; }int main() {read(n), read(K);rep(i, 1, n) read(a[i]), pre[i] = pos[a[i]], pos[a[i]] = i;rep(j, 1, K) {build(1, 0, n);rep(i, 1, n) update(1, 0, n, pre[i], i - 1), dp[i] = query(1, 0, n, 0, i - 1);}printf("%d", dp[n]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/aziint/p/9167894.html

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 833B The Bakery的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。