【斜率优化dp】K-Anonymous Sequence

动态规划DP

传送门：POJ3709

题意：给定一个数列，每次可以花费1的代价使某个数减1，求使每个数都至少和k-1个数相同的最小代价

思路：

  • 用$f_i$记录到第i位满足条件的最小代价；$pre_i$表示到第i为的前缀和；

  • $f_i=\min\limits {1\leqslant j\leqslant i-k+1} {f{j-1}+pre_i-pre_j+(i-j)\times a_j}$

注意：

  • INF不要太小；
  • 横坐标相同时注意特盼；

代码如下：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
#define N 1000000
#define INF 0x3f3f3f3f
LL t,n,m,tt,ww,q[N],f[N],a[N],s[N],x[N],y[N];
inline double K(int u,int v){return (double)(y[u]-y[v])/(x[u]-x[v]);}
int main(){
	scanf("%lld",&t);
	while (t--){
		scanf("%lld%lld",&n,&m);
		for (LL i=1;i<=n;i++){scanf("%lld",&a[i]); s[i]=s[i-1]+a[i];}
		memset(f,INF,sizeof f);
		memset(q,0,sizeof q); tt=1; ww=1; q[1]=1; x[1]=a[1]; y[1]=0; f[0]=0;
		for (LL i=2;i<=n;i++){			
			LL j=i-m+1;
			if (j>m){
				while (tt<=ww && x[q[ww]]==x[j] && y[q[ww]]>=y[j]) ww--;
				while (tt<ww && K(j,q[ww])<=K(q[ww-1],q[ww])) ww--;
				if (tt>ww || (tt<=ww && x[q[ww]]!=x[j])) q[++ww]=j;
			}
			while (tt<ww && K(q[tt],q[tt+1])<i) tt++;
			if (tt<=ww){j=q[tt]; f[i]=-x[j]*i+y[j]+s[i];}
			x[i]=a[i]; y[i]=f[i-1]-s[i]+a[i]*i;
		}
		if (m==1) puts("0"); else printf("%lld\n",f[n]);
	}
	
	return 0;
}