题意：
给长度为n的非严格递增数列a0,a1…an-1,每一次操作可以使数列中的任何一项的值减小1。现在要使数列中每一项都满足其他项中至少有k-1项和它相等。求最少操作次数。
分析：
dp[i]:=只考虑前i项情况下，满足要求的最小操作次数。
s[i]:=a0+a1+…+ai,则dp[i]=min(dp[j]+s[i]-s[j]-aj*(i-j))(0<=j<=i-k)，，可以看做dp[i]是这i-k+1条直线在x=i出的最小值，从而进行斜率优化。
代码：
//poj 3709//sep9#include <iostream>using namespace std;const int maxN=500012;typedef long long ll;int n,k; ll dp[maxN];ll a[maxN];ll sum[maxN];int deq[maxN];ll f(int j,int x){return -a[j]*x+dp[j]-sum[j]+a[j]*j;}bool check(int f1,int f2,int f3){ll a1=-a[f1],b1=dp[f1]-sum[f1]+a[f1]*f1;ll a2=-a[f2],b2=dp[f2]-sum[f2]+a[f2]*f2;ll a3=-a[f3],b3=dp[f3]-sum[f3]+a[f3]*f3;return (a2-a1)*(b3-b1)>=(a1-a3)*(b1-b2);}int main(){int T;scanf("%d",&T);while(T–){scanf("%d%d",&n,&k);sum[0]=0;for(int i=0;i<n;++i){scanf("%lld",&a[i]);sum[i+1]=sum[i]+a[i];}int s=0,t=1;deq[0]=0;dp[0]=0;for(int i=k;i<=n;++i){if(i-k>=k){while(s+1<t&&check(deq[t-2],deq[t-1],i-k)) t–;deq[t++]=i-k;}while(s+1<t&&f(deq[s],i)>=f(deq[s+1],i)) ++s;dp[i]=sum[i]+f(deq[s],i);}printf("%lld\n",dp[n]);}return 0;}
生活不要太劳累，弄得自己很疲惫，快乐幸福多体会，
