hdu 3045 Picnic Cows

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3045

题目思路：比较典型的斜率优化dp,不过我敲错了好多次啊！后来打了1千组数据才发现，原来y[i]不单调，x[i]又有相同值，这样如果只在小于时才删除点的话，就可能出现有些点永远不能删去，即在相同x上出现三个点上升又下降的情况。比如这组数据1 2 3 3 3 4 5，所以在小于或等于时都要删点才行啊！

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
struct node
{
    __int64 x,y;
}q[400010];
int n,m;
__int64 dp[400010];
__int64 sum[400010],a[400010];
int rec;
int main()
{
   int i;
   while(scanf("%d%d",&n,&m)!=EOF)
   {
       for(i=1;i<=n;i++)
            scanf("%I64d",&a[i]);
        sort(a+1,a+n+1);
        sum[0]=0;
        for(i=1;i<=n;i++)
            sum[i]=sum[i-1]+a[i];
        int top=0,tail=0;
        q[0].x=a[1];q[0].y=0;
        tail++;
        for(i=m;i<=n;i++)
        {
            if(i-m>=m)
            {
                node tmp;
                tmp.x=a[i-m+1];
                tmp.y=dp[i-m]+(i-m)*a[i-m+1]-sum[i-m];
                while(tail-top>=2&&(tmp.y-q[tail-2].y)*(q[tail-1].x-q[tail-2].x)<=
                      (q[tail-1].y-q[tail-2].y)*(tmp.x-q[tail-2].x))//一定要是小于等于，不然会wrong.
                    tail--;
                q[tail++]=tmp;
            }
            while(tail-top>=2&&(q[top+1].y-q[top].y)<=i*(q[top+1].x-q[top].x))
                top++;
            dp[i]=q[top].y-i*q[top].x+sum[i];
        }
        printf("%I64d\n",dp[n]);
   }
}