艹了天天都被不知道的知识点教育，知道的又做不出来。 :lei:
在动态规划中，决策单调性指对于$j < j'$，$f(j')$的最佳转移$f(i')$位置$i'$一定不小于$f(j)$的$i$。
假设
$$f(r)=\min{f(k-1)+w(k,r)}$$
为了证明这一点，首先假设
$$f(r)=f(k-1)+w(k,r)$$
此时我们有$\forall i < k$，
$$f(k-1)+w(k,r) < f(i-1)+w(i,r)$$
此后，将r后挪1。我们必须要证明$\forall i < k$，
$$f(k-1)+w(k,r+1) < f(i-1)+w(i,r+1)$$
也就是证明对于两边的两个增量$\Delta$有
$$w(k,r+1) - w(k,r) < w(i,r+1) - w(i,r)$$
使用分治
一旦有决策单调性了，我们就可以通过优于$n^2$的总复杂度完成规划。
例如使用分治。当我们找到区间$[ l, r ]$的中点$m$的决策点$p$时，那么$[l, m-1]$区间只能从不晚于$p$转移，$[m+1, r]$只能从不早于$p$转移。
l和r是当前要决策的区间，L和R是转移位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void solve(int l,int r,int L,int R) {
if(l>r)return;
int mid=(l+r)/2;
int p=0;
for(int i=L;i<=min(mid,R);i++){
//这里的下标写法要和方程配套
if(f[i-1]+w[i,mid]<f[mid]){
f[mid]=f[i-1]+w[i,mid];
p=i;
}
}
solve(l,mid-1,L,p);
solve(mid+1,r,p,R);
}
|
【CF868F】yts1999 Doing Minimization
You are given an array of n integers a1… an. The cost of a subsegment is the number of unordered pairs of distinct indices within the subsegment that contain equal elements. Split the given array into k non-intersecting non-empty subsegments so that the sum of their costs is minimum possible. Each element should be present in exactly one subsegment.
分析
设$f(i,j)$表示前j个分i段。
这个题目就满足决策单调。一个更长的区间+1之后只有可能比短的区间增加更多的代价。
接下来的问题是怎么算这道题里的$w(i,j)$。$n^2$显然不行。看到有人整了个类似莫队的东西，不过我还没太弄明白这个复杂度是怎么算的，看起来是和分治的内层循环一致所以就对复杂度没有更多的贡献了。
一共进行k轮分治，$O(kn\log n)$
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
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using ll=long long;
const int XN=100010;
ll f[30][XN];
ll wage;
int cl,cr;
int num[XN];
ll cnt[XN];
void jump(int l,int r){
while(cl<l){
cnt[num[cl]]--;
wage-=cnt[num[cl]];
cl++;
}
while(l<cl){
cl--;
wage+=cnt[num[cl]];
cnt[num[cl]]++;
}
while(r<cr){
cnt[num[cr]]--;
wage-=cnt[num[cr]];
cr--;
}
while(cr<r){
cr++;
wage+=cnt[num[cr]];
cnt[num[cr]]++;
}
}
void solve(int l,int r,int L,int R,int k) {
if(l>r)return;
int mid=(l+r)/2;
int p=0;
for(int i=L;i<=min(mid,R);i++){
jump(i,mid);
if(f[k-1][i-1]+wage<f[k][mid]){
f[k][mid]=f[k-1][i-1]+wage;
p=i;
}
}
solve(l,mid-1,L,p,k);
solve(mid+1,r,p,R,k);
}
int main(){
ios::sync_with_stdio(false);
int n,kk;cin>>n>>kk;
for(int i=1;i<=n;i++)cin>>num[i];
memset(f,0x3f,sizeof(f));
for(auto & i : f)i[0]=0;
for(int i=1;i<=n;i++){
wage+=cnt[num[i]];
cnt[num[i]]++;
f[1][i]=wage;
}
// for(int i=1;i<=n;i++){
// cout<<f[1][i]<<' ';
// }
// cout<<endl;
wage=0;cl=1;cr=0;
memset(cnt,0,sizeof(cnt));
for(int i=2;i<=kk;i++){
solve(1,n,1,n,i);
}
cout<<f[kk][n]<<endl;
}
|