斜率dp
斜率dp都不大好写啊,细节的边界处理感觉好麻烦啊。
这里我们很容易就总结出状态和状态转移方程了。
我们首先从小到大排序(在斜率dp中排序很重要,有利于保持决策的单调性)
dp[i] 表示到第i个点为止的最小花费。
dp[i] = min(dp[j-1]+sum[i]-sum[j]-(i-j+1)a[j])
注意范围t+1<=j<=i-t+1
那么我们就对这个公式进行斜率dp的优化就行了,把他变为O(n)
但是要注意的是起始的初始状态。
如果i<t的时候怎么办,很显然这时是不可能的。
那么当i<2t时怎么办?很显然这时我们必须一起打包买走的。
处理好初始情况,我们就可以解题了
#include<iostream> #include<algorithm> #include<deque> using namespace std; const int max_n = 4e5+100; int n,t; typedef __int64 ll; const ll inf = 1e18; ll a[max_n],sum[max_n],dp[max_n]; bool check(int p1,int p2,int k){ ll x1 = a[p1],y1 = dp[p1-1]-sum[p1-1]+(p1-1)*a[p1]; ll x2 = a[p2],y2 = dp[p2-1]-sum[p2-1]+(p2-1)*a[p2]; return (y2-y1)<=k*(x2-x1); } bool check2(int p1,int p2,int p3){ ll x1 = a[p1],y1 = dp[p1-1]-sum[p1-1]+(p1-1)*a[p1]; ll x2 = a[p2],y2 = dp[p2-1]-sum[p2-1]+(p2-1)*a[p2]; ll x3 = a[p3],y3 = dp[p3-1]-sum[p3-1]+(p3-1)*a[p3]; return (y2-y1)*(x3-x2)>=(y3-y2)*(x2-x1); } int main(){ while (~scanf("%d %d",&n,&t)){ for (int i=1;i<=n;++i)scanf("%lld",&a[i]); sort(a+1,a+1+n); for (int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i]; deque<int> que; for (int i=t;i<2*t&&i<=n;++i)dp[i]=sum[i]-a[1]*i; for (int i=2*t;i<=n;++i){ int k = i; while (que.size()>=2&&check2(que[que.size()-2],que[que.size()-1],i+1-t))que.pop_back(); que.push_back(i-t+1); while (que.size()>=2&&check(que[0],que[1],k))que.pop_front(); int j = que.front(); dp[i]=dp[j-1]+sum[i]-sum[j-1]-(i-j+1)*a[j]; } printf("%lld\n",dp[n]); } }