CF868F Yet Another Minimization Problem

发表于 | 阅读数

题目描述：给定一个序列 $a$，要把它分成 $k$ 个子段。每个子段的费用是其中相同元素的对数。求所有子段的费用之和的最小值。

$(k\leq 20)$

显然可以设出

考虑$w(l,r)$

$w(l-1,r)+w(l,r+1)\leq w(l,r)+w(l+1,r+1)$

因为$a[l-1],a[r+1]$可能新产生对子，然后就可以套板子了。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e5 + 10;
const int mod = 1e9 + 7;

int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + c - '0', c = getchar();
return x \* f;
}
int a[N];
ll dp[N][21], cnt[N];
int L, R;

ll val;
ll w(int l, int r)
{
while (L > l)
val += cnt[a[--L]], cnt[a[L]]++;
while (R < r)
val += cnt[a[++R]], cnt[a[R]]++;
while (L < l)
val -= --cnt[a[L++]];
while (R > r)
val -= --cnt[a[R--]];
return val;
}
void solve(int l, int r, int A, int B, int k)
{
if (r < l)
return;

    int mid = (l + r) >> 1;

    int p = 0;
    for (int i = A; i <= min(mid, B); i++)
        if (w(i, mid) + dp[i - 1][k - 1] < dp[mid][k])
        {
            dp[mid][k] = w(i, mid) + dp[i - 1][k - 1];
            p = i;
        }
    solve(l, mid - 1, A, p, k);
    solve(mid + 1, r, p, B, k);

}
int main()
{
int n = read(), m = read();
for (int i = 1; i <= n; i++)
a[i] = read();
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
L = 1, R = 0;
for (int j = 1; j <= m; j++)
{
solve(1, n, 1, n, j);
}

    cout << dp[n][m] << endl;

}

</details>
```