hdu3045 Picnic Cows（斜率优化DP）

题意：

有n个奶牛分别有对应的兴趣值，现在对奶牛分组，每组成员不少于t，

在每组中所有的成员兴趣值要减少到该组的最小值，问总共最少需要减少的兴趣值是多少。

思路：

斜率优化+DP
转移方程为：f[i]=min{ f[j]+sum[i]-sum[j]+(i-j)*a[j+1] } T<=j<=i-T
其中sum表示a的前缀和。
如果j>k且决策j优于决策k则有
f[j]-f[k]+sum[k]-sum[j]-k*a[k+1]+j*a[j+1]<i*(a[j+1]-a[k+1])
维护指定区间内的下凸包即可。
需要注意的是输入输出用int64，而且斜率部分不能用之前直接除的写法了，因为a有long long，可能误差会比较大，改用化除为乘的方法。

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define mem(a) memset(a,0,sizeof(a))
 5 #define mp(x,y) make_pair(x,y)
 6 const int INF = 0x3f3f3f3f;
 7 const ll INFll = 0x3f3f3f3f3f3f3f3fll;
 8 inline ll read(){
 9     ll x=0,f=1;char ch=getchar();
10     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
12     return x*f;
13 }
14 //////////////////////////////////////////////////////////////////////////
15 const int maxn = 4e5+10;
16 
17 int L,R,n,T,q[maxn];
18 ll a[maxn],dp[maxn],sum[maxn];
19 
20 ll getup(int j,int k){
21     return dp[j]-dp[k]-sum[j]+sum[k]+j*a[j+1]-k*a[k+1];
22 }
23 ll getdown(int j,int k){
24     return a[j+1]-a[k+1];
25 }
26 
27 int main(){
28     while(scanf("%d%d",&n,&T)==2){
29         dp[0]=sum[0]=0;a[0]=0;
30         for(int i=1; i<=n; i++)
31             scanf("%I64d",&a[i]);
32         sort(a+1,a+1+n);
33         for(int i=1; i<=n; i++)
34             sum[i] = sum[i-1]+a[i];
35 
36         int L=0,R=0;
37         for(int i=1; i<=n; i++){
38             while(L<R && getup(q[L+1],q[L]) <= i * getdown(q[L+1],q[L])) L++;
39             int j = q[L];
40             dp[i] = dp[j]+(sum[i]-sum[j])-(i-j)*a[j+1];
41             int t = i-T+1;
42 // 从t~i是一组， T是最小的长度， 所以要考虑R与第t个比较，如果与t+1比较，那可能会
43 //把第t个弹出，就不可能是最优解了，也就是不能形成长度为>=T的按顺序的一段。
44             if(t >= T){
45                 while(L<R && getup(t,q[R])*getdown(q[R],q[R-1]) <= getup(q[R],q[R-1])*getdown(t,q[R]))
46                     R--;
47                 q[++R] = t;    
48             }
49         }
50 
51         printf("%I64d
",dp[n]);
52     }
53 
54     return 0;
55 }