本文共 3174 字，大约阅读时间需要 10 分钟。

原题链接：

题意

给了一个长度为n的序列，其中$Cost(t)={\sum }_{x\in set(t)}last(x)-first(x)$，我们可以将序列分成k段，问minCost是多少

分析

不难想到dp的状态$dp[i][j]$代表前i个数分成j组时的最小花费，然后先推出一个暴力的DP方程

$$dp[i][j]=min(d[k][j-1]+val(k+1,i))k\in [0,j-1]$$

$$val(i,j)代表从[i,j]区间的花费$$

如果直接暴力去找肯定是超时的，这时候就可以用数据结构去优化DP。首先考虑怎么算区间内的花费，我们记录一个last[x]表示这个数前一次出现的位置，然后存入$i-last[x]$，统计区间和，这样就可以算出每个数最晚出现和最早出现之差，但这样是有问题的，因为有些数的$last[x]<k+1$，这样的值对于区域是没有贡献的，因此我们倒过来考虑，去累加当前x对哪些区间有影响。$last[x]>=k+1$推出$k<=last[x]-1$，也就是说当前i对$[0,last[x]-1]$有$i-last[x]$的贡献。

Code

#include 
   
    using namespace std;#define fi first#define se second#define re registertypedef long long ll;typedef pair
    
      PII;typedef unsigned long long ull;const int N = 35005 + 20, M = 1e6 + 5, INF = 0x3f3f3f3f;const int MOD = 1e9+9;int dp[N];int a[N], last[N], pre[N];struct node {
       int l, r;    int sum, tag;}t[N<<2];void push_up(int u) {
       t[u].sum = min(t[u<<1].sum, t[u<<1|1].sum);}void push_down(int u) {
       if (t[u].tag) {
           t[u<<1].tag += t[u].tag;        t[u<<1|1].tag += t[u].tag;        t[u<<1].sum += t[u].tag;        t[u<<1|1].sum += t[u].tag;        t[u].tag = 0;    }}void build(int u, int l, int r) {
       t[u].l = l, t[u].r = r, t[u].tag = 0, t[u].sum = INF;    if (l == r) {
           t[u].sum = dp[l];        return;    }    int mid = (l + r) >> 1;    build(u<<1, l, mid);    build(u<<1|1, mid+1, r);    push_up(u);}void modify(int u, int ql, int qr, int val) {
       if (ql <= t[u].l && qr >= t[u].r) {
           t[u].sum += val;        t[u].tag += val;        return;    }    push_down(u);    int mid = (t[u].l + t[u].r) >> 1;    if (ql <= mid) modify(u<<1, ql, qr, val);    if (qr > mid) modify(u<<1|1, ql, qr, val);    push_up(u);}int query(int u, int ql, int qr) {
       if (ql <= t[u].l && qr >= t[u].r) return t[u].sum;    int mid = (t[u].l + t[u].r) >> 1;    int ans = INF;    push_down(u);    if (ql <= mid) ans = min(ans, query(u<<1, ql, qr));    if (qr > mid) ans = min(ans, query(u<<1|1, ql, qr));    return ans;}void solve() {
       int n, k; cin >> n >> k;    for (int i = 1; i <= n; i++) {
           cin >> a[i];        if (!last[a[i]]) pre[i] = i;        else pre[i] = last[a[i]];        last[a[i]] = i;    }    memset(dp, 0x3f, sizeof dp);    dp[0] = 0;    for (int i = 1; i <= k; i++) {
           build(1, 0, n);        for (int j = 1; j <= n; j++) {
               int p = pre[j];            int val = j - p;            modify(1, 0, p-1, val);            dp[j] = query(1, 0, j-1);        }    }    cout << dp[n] << endl;}signed main() {
       ios::sync_with_stdio(0);    cin.tie(0);    cout.tie(0);#ifdef ACM_LOCAL    freopen("input", "r", stdin);    freopen("output", "w", stdout);#endif    solve();}
    
   

转载地址：https://blog.csdn.net/kaka03200/article/details/117228920 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！