题目
定义状态dp[i]表示排序后前i个数分组后的最小代价。
dp[i] = min(dp[j]+sum[i] – sum[j] – a[j+1]*(i-j))
dp[i] = min(dp[j]-sum[j]+a[j+1]*j) + sum[i] – a[j+1]*i
dp[j]-dp[k]+sum[k]-sum[j]+j*a[j+1]-k*a[k+1] < i*(a[j+1]-a[k+1])
只需要用斜率优化即可。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define N 400010
int q[N];
LL sum[N], dp[N], a[N];
int n, T, l, r;
LL gx(int i, int j){return a[i+1]-a[j+1];
}
LL gy(int i, int j){return dp[i]-sum[i]+i*a[i+1]-(dp[j]-sum[j]+j*a[j+1]);
}LL cmp( int a, int b){return a < b;
}
LL gdp(int i, int j){return dp[j]+(sum[i]-sum[j])-a[j+1]*(i-j);
}
int main(){while ( scanf( "%d%d", &n, &T)!=EOF ){for ( int i = 1; i <= n; i++) scanf( "%lld", &a[i]);sort(a+1, a+1+n, cmp);for ( int i = 1; i <= n; i++) sum[i] = sum[i-1]+a[i];sum[0]=dp[0]=a[0]=0;l = 0, r = 0, q[r++] = 0;for ( int i = 1; i <= n; i++){int k = i;for (; l+1 < r && gy(q[l+1],q[l]) <= i*gx(q[l+1],q[l]);l++);dp[i] = gdp(i, q[l]);int j = i - T + 1;if(j < T) continue; for (; l+1 < r && gy(j, q[r-1])*gx( q[r-1], q[r-2]) <= gy(q[r-1],q[r-2])*gx(j,q[r-1]) ;r--);q[r++] = j;} printf( "%lld\n", dp[n]);}return 0;
}