【CF868F】Yet Another Minimization Problem (决策单调性优化dp+分治)

description

点击查看题目

solution

code

设 d p i , j dp_{i,j} dpi,j​:把前 i i i个数划分 j j j段的最小花费, w i , j w_{i,j} wi,j​: [ i , j ] [i,j] [i,j]划分为一段的花费
d p i , j = m i n ( d p [ k ] [ j − 1 ] + w [ k + 1 ] [ i ] ) , k < i dp_{i,j}=min(dp[k][j-1]+w[k+1][i]),k<i dpi,j​=min(dp[k][j−1]+w[k+1][i]),k<i

而这个转移是具有决策单调性的
换言之, ∀ i 1 < i 2 \forall i_1<i_2 ∀i1​<i2​,且 i 1 i_1 i1​由 k 1 k_1 k1​转移而来, i 2 i_2 i2​由 k 2 k_2 k2​转移而来,则必有 k 1 ≤ k 2 k_1\le k_2 k1​≤k2​

证明一下,假设 k 1 > k 2 k_1>k_2 k1​>k2​
由条件可以列得
{ d p ( k 1 , j − 1 ) + w ( k 1 + 1 , i 1 ) ≤ d p ( k 2 , j − 1 ) + w ( k 2 + 1 , i ) d p ( k 2 , j − 1 ) + w ( k 2 + 1 , i 2 ) ≤ d p ( k 1 , j − 1 ) + w ( k 1 + 1 , i ) \left\{ \begin{aligned} dp(k_1,j-1)+w(k_1+1,i_1) \le dp(k_2,j-1)+w(k_2+1,i)\\ dp(k_2,j-1)+w(k_2+1,i_2)\le dp(k_1,j-1)+w(k_1+1,i)\\ \end{aligned} \right. {dp(k1​,j−1)+w(k1​+1,i1​)≤dp(k2​,j−1)+w(k2​+1,i)dp(k2​,j−1)+w(k2​+1,i2​)≤dp(k1​,j−1)+w(k1​+1,i)​
假设两个式子都是取的 = = =,那么交换 k 1 , k 2 k_1,k_2 k1​,k2​不影响
否则至少有一个取了 < < <,不防假设
{ d p ( k 1 , j − 1 ) + w ( k 1 + 1 , i 1 ) ≤ d p ( k 2 , j − 1 ) + w ( k 2 + 1 , i ) d p ( k 2 , j − 1 ) + w ( k 2 + 1 , i 2 ) < d p ( k 1 , j − 1 ) + w ( k 1 + 1 , i ) \left\{ \begin{aligned} dp(k_1,j-1)+w(k_1+1,i_1) \le dp(k_2,j-1)+w(k_2+1,i)\\ dp(k_2,j-1)+w(k_2+1,i_2)< dp(k_1,j-1)+w(k_1+1,i)\\ \end{aligned} \right. {dp(k1​,j−1)+w(k1​+1,i1​)≤dp(k2​,j−1)+w(k2​+1,i)dp(k2​,j−1)+w(k2​+1,i2​)<dp(k1​,j−1)+w(k1​+1,i)​
移项得
{ w ( k 1 + 1 , i 1 ) − w ( k 2 + 1 , i 1 ) ≤ d p ( k 2 , j − 1 ) − d p ( k 1 , j − 1 ) d p ( k 2 , j − 1 ) − d p ( k 1 , j − 1 ) < w ( k 1 + 1 , i 2 ) − w ( k 2 + 1 , i 2 ) \left\{ \begin{aligned} w(k_1+1,i_1)-w(k_2+1,i_1) \le dp(k_2,j-1)-dp(k_1,j-1)\\ dp(k_2,j-1)-dp(k_1,j-1)< w(k_1+1,i_2)-w(k_2+1,i_2)\\ \end{aligned} \right. {w(k1​+1,i1​)−w(k2​+1,i1​)≤dp(k2​,j−1)−dp(k1​,j−1)dp(k2​,j−1)−dp(k1​,j−1)<w(k1​+1,i2​)−w(k2​+1,i2​)​
所以有
w ( k 1 + 1 , i 1 ) − w ( k 2 + 1 , i 1 ) < w ( k 1 + 1 , i 2 ) − w ( k 2 + 1 , i 2 ) w(k_1+1,i_1)-w(k_2+1,i_1)< w(k_1+1,i_2)-w(k_2+1,i_2) w(k1​+1,i1​)−w(k2​+1,i1​)<w(k1​+1,i2​)−w(k2​+1,i2​)
再移项,最后得
w ( k 2 + 1 , i 1 ) − w ( k 1 + 1 , i 1 ) > w ( k 2 + 1 , i 2 ) − w ( k 1 + 1 , i 2 ) w(k_2+1,i_1)-w(k_1+1,i_1)> w(k_2+1,i_2)-w(k_1+1,i_2) w(k2​+1,i1​)−w(k1​+1,i1​)>w(k2​+1,i2​)−w(k1​+1,i2​)
这显然是不成立的,因为 i 1 < i 2 i_1<i_2 i1​<i2​,而 w w w是跟区间内相同权值的个数组合数有关
不等号右边的增长应更快,假设不成立;证明的确具有决策单调性

分治处理,注意决策点可能并不一定是正中间,可能会有所偏移,直接枚举即可

#include <cstdio>
#include <cstring>
#define inf 1e18
#define maxn 100005
#define int long long
int n, K, k, curl = 1, curr, cost;
int a[maxn], cnt[maxn];
int dp[maxn][25];

void Delete( int x ) {
	cost = cost - cnt[a[x]] + 1;
	cnt[a[x]] --;
}

void Add( int x ) {
	cost = cost + cnt[a[x]];
	cnt[a[x]] ++;
}

void calc( int l, int r ) {
	while( curl < l ) Delete( curl ++ );
	while( l < curl ) Add( -- curl );
	while( curr < r ) Add( ++ curr );
	while( r < curr ) Delete( curr -- );
}

//计算[L,R]区间的dp值 决策点枚举范围为[l,r]
void solve( int L, int R, int l, int r ) {
	if( L > R || l > r ) return;
	int mid = ( L + R ) >> 1, pos, ans = inf;
	for( int i = l;i <= r;i ++ ) {
		calc( i + 1, mid );
		if( ans > dp[i][k - 1] + cost ) 
			ans = dp[i][k - 1] + cost, pos = i;
	}
	dp[mid][k] = ans;
	solve( L, mid - 1, l, pos );
	solve( mid + 1, R, pos, r );
}

signed main() {
	memset( dp, 0x7f, sizeof( dp ) );
	dp[0][0] = 0;
	scanf( "%lld %lld", &n, &K );
	for( int i = 1;i <= n;i ++ )
		scanf( "%lld", &a[i] );
	for( k = 1;k <= K;k ++ ) solve( 1, n, 0, n - 1 );
	//决策点i表示[j,i]为一个子段,[i+1,k]为一个子段
	//所以决策点范围是[0,n-1]而不是[1,n]
	printf( "%lld\n", dp[n][K] );
	return 0;
}
上一篇:Python-最小化卡方


下一篇:python – SciPy优化器忽略其中一个约束