E. Partition Game_牛客博客

思路：
设 $dp[i][j]$ 表示前 $i$ 个数分成 $j$ 段的最小花费，那么显然有 $dp[i][j]=min(dp[k][j-1]+cost(k+1,i)),k<i$

一个 $dp$ 满足决策单调性的充要条件是：对于两个决策点 $𝑥<𝑦$ ，若在 $i$ 处 $y$ 优于 $x$ ，则在 $[𝑖+1,𝑛]$ 处 $y$ 都优于 $x$ 。
定理：若 $w$ 满足四边形不等式，则 $dp$ 满足决策单调性。
定义：若二元函数 $w$ 满足 $∀𝑎<𝑏≤𝑐<𝑑,𝑤(𝑎,𝑐)+𝑤(𝑏,𝑑)≤𝑤(𝑏,𝑐)+𝑤(𝑎,𝑑)$ ，则称其满足四边形不等式。
推论，若 $w$ 只与 $i$ 有关，即 $w(i)$ ，则必然符合四边形不等式。且此时，该类 $dp$ 适宜用单调队列优化。

而这题是满足 $cost(i,j)+cost(i+1,j+1)≤cost(i+1,j)+cost(i,j+1)$ 的，若 $x$ 在 $i、j+1$ 都出现了，则不等式右边比左边多出 $j+1-i$ 的贡献，其它情况一样。假设区间 $[l,r]$ 的中点为 $mid$ 、决策区间为 $[x,y]$ ，那么 $solve(l,r,x,y)$ 可以先求出 $f[mid][j]$ ，并得到最优决策点 $pos$ ；接着递归处理 $solve(l,mid-1,x,pos);solve(mid+1,r,pos,y);$

注意到每次递归处理时决策区间的左端点是递增的，所以我们有了莫队的思路，而左端点递增保证了其一层的移动指针复杂度是线性的。暴力更新 $cost(k+1,i)$ 值的复杂度平摊下来是 $O(1)$ 。

MyCode：

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e4;
int f[maxn][105],last[maxn],nex[maxn],pre[maxn],a[maxn];
int now,pl=1,pr,sum;
int cost(int l,int r) {
    while(pl<l) {
        if(nex[pl]<=pr) sum-=nex[pl]-pl;
        pl+=1;
    }
    while(pl>l) {
        pl-=1;
        if(nex[pl]<=pr) sum+=nex[pl]-pl;
    }
    while(pr>r) {
        if(pre[pr]>=pl) sum-=pr-pre[pr];
        pr-=1;
    }
    while(pr<r) {
        pr+=1;
        if(pre[pr]>=pl) sum+=pr-pre[pr];
    }
    return sum;
}//莫队
void solve(int l,int r,int x,int y) {
    if( l>r ) return;
    int mid=l+r>>1,tmp,val=0x3f3f3f3f,pos;
    for(int i=x;i<mid&&i<=y;++i) {
        tmp=f[i][now-1]+cost(i+1,mid);
        if(tmp<val) val=tmp,pos=i;
    }
    f[mid][now]=val;
    solve(l,mid-1,x,pos);
    solve(mid+1,r,pos,y);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;++i) {
        cin>>a[i];
        pre[i]=last[a[i]];
        last[a[i]]=i;
    }
    for(int i=1;i<=n;++i) {
        last[a[i]]=n+1;
        f[i][0]=0x3f3f3f3f;
    }//f[0][0]=0
    for(int i=n;i;--i) {
        nex[i]=last[a[i]];
        last[a[i]]=i;
    }
    for(int i=1;i<=k;++i) now=i,solve(1,n,0,n);
    cout<<f[n][k]<<'\n';
    return 0;
}