E. Partition Game
首先肯定可以想到dp
[dp[i][j] = min(dp[p][j - 1] + val(p + 1 , i))
]
dp表示前i个被分成j块，那么肯定要枚举上一块的尾节点，然后算一下val(p + 1 , i)表示(p + 1 , i)这一段的贡献值是多少。
-
对于一段来说[L , R] , 其中不同的a[i]值贡献都是独立的
-
那么对于一个a[i] = x来说，其存在于X[1] , X[2] , X[3] , ..... X[m] 位置上。
那么它的贡献等于X[m] - X[1] = X[2] - X[1] + X[3] - X[2] +......+ X[m] - X[m - 1]
那么对于这个公式，我们只需要对每个点求一个i - last[i] , last[i] 表示 上一个a[i]出现的位置。
-
从最上面的dp递推公式来看,我们只需要看一下val(p + 1 , i)的贡献值,
但是因为不是很好算，因为既需要枚举i，又需要枚举p。
所以就直接先枚举k，然后枚举i来更新dp。
那么怎么更新呢。
根据2里面的公式，只需要每个点的x = i - last[i]，把x加到它被h < i中需要的h上面。
对于h >= 1 && h < last[i] , 这个部分都是需要的，因为[last[i] , i]这一对在last[i] - 1右边，可以产生贡献，但是h >= last[i] && h <= i 的这一部分不需要，因为在这个h右边，last[i]不存在。
这就形成了区间加，并且当前dp需要最小值，所以线段树求解dp
// #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
// #pragma GCC optimize(3 , "Ofast" , "inline")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <stack>
#include <set>
#include <bitset>
#include <deque>
using namespace std ;
#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y second
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair<int , int> PII ;
const int N = 37000 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
int n , m , minx[N << 2] , lazy[N << 2] , dp[N] ;
void up(int rt) {
minx[rt] = min(minx[ls] , minx[rs]) ;
}
void down(int rt) {
if(lazy[rt]) {
lazy[ls] += lazy[rt] ;
lazy[rs] += lazy[rt] ;
minx[ls] += lazy[rt] ;
minx[rs] += lazy[rt] ;
minx[rt] = min(minx[ls] , minx[rs]) ;
lazy[rt] = 0 ;
}
return ;
}
void build(int rt , int l , int r) {
minx[rt] = INF , lazy[rt] = 0 ;
if(l == r) {
minx[rt] = dp[l] ;
return ;
}
int mid = l + r >> 1 ;
build(ls , l , mid) ;
build(rs , mid + 1 , r) ;
up(rt) ;
}
void update(int rt , int l , int r , int ql , int qr , int k) {
if(qr <= 0 || qr < ql) return ;
if(ql <= l && r <= qr) {
minx[rt] += k ;
lazy[rt] += k ;
return ;
}
down(rt) ;
int mid = l + r >> 1 ;
if(ql <= mid) update(ls , l , mid , ql , qr , k) ;
if(qr > mid) update(rs , mid + 1 , r , ql , qr , k) ;
up(rt) ;
}
int ask(int rt , int l , int r , int ql , int qr){
if(qr <= 0) return 0 ;
if(ql <= l && r <= qr) return minx[rt] ;
int mid = l + r >> 1 , ans = INF ;
down(rt) ;
if(ql <= mid) ans = ask(ls , l , mid , ql , qr) ;
if(qr > mid) ans = min(ans , ask(rs , mid + 1 , r , ql , qr)) ;
return ans ;
}
int k , a[N] , last[N] , mp[N] ;
int work()
{
cin >> n >> k ;
for(int i = 1; i <= n ;i ++ ) {
cin >> a[i] ;
last[i] = mp[a[i]] ;
mp[a[i]] = i ;
dp[i] = dp[i - 1] ;
if(last[i]) dp[i] += i - last[i] ;
}
for(int j = 2; j <= k ; j ++ ) {
build(1 , 1 , n) ;
for(int i = j ;i <= n ;i ++ ) {
update(1 , 1 , n , 1 , last[i] - 1 , i - last[i]) ;
dp[i] = ask(1 , 1 , n , 1 , i - 1) ;
}
}
cout << dp[n] << "
" ;
return 0 ;
}
int main()
{
// freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
// freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;
work() ;
return 0 ;
}
/*
*/