HDU3045 Picnic Cows —— 斜率优化DP

题目链接：https://vjudge.net/problem/HDU-3045

Picnic Cows

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3491    Accepted Submission(s): 1124

Problem Description

It’s summer vocation now. After tedious milking, cows are tired and wish to take a holiday. So Farmer Carolina considers having a picnic beside the river. But there is a problem, not all the cows consider it’s a good idea! Some cows like to swim in West Lake, some prefer to have a dinner in Shangri-la ,and others want to do something different. But in order to manage expediently, Carolina coerces all cows to have a picnic!
Farmer Carolina takes her N (1<N≤400000) cows to the destination, but she finds every cow’s degree of interest in this activity is so different that they all loss their interests. So she has to group them to different teams to make sure that every cow can go to a satisfied team. Considering about the security, she demands that there must be no less than T(1<T≤N)cows in every team. As every cow has its own interest degree of this picnic, we measure this interest degree’s unit as “Moo~”. Cows in the same team should reduce their Moo~ to the one who has the lowest Moo~ in this team——It’s not a democratical action! So Carolina wishes to minimize the TOTAL reduced Moo~s and groups N cows into several teams.
For example, Carolina has 7 cows to picnic and their Moo~ are ‘8 5 6 2 1 7 6’ and at least 3 cows in every team. So the best solution is that cow No.2,4,5 in a team (reduce (2-1)+(5-1) Moo~)and cow No.1,3,6,7 in a team (reduce ((7-6)+(8-6)) Moo~),the answer is 8.

 

Input

The input contains multiple cases.
For each test case, the first line has two integer N, T indicates the number of cows and amount of Safe-base line.
Following n numbers, describe the Moo~ of N cows , 1st is cow 1 , 2nd is cow 2, and so on.

 

Output

One line for each test case, containing one integer means the minimum of the TOTAL reduced Moo~s to group N cows to several teams.

 

Sample Input

7 3 8 5 6 2 1 7 6

 

Sample Output

8

 

Source

2009 Multi-University Training Contest 14 - Host by ZJNU

 

Recommend

gaojie

 

题意：

有n头牛去野营，烧烤，吃什么，牛肉？细思极恐。不扯了。将这n头牛分成若干组，且每一组至少要有T头。每头牛都有一个值，一个组的值是这个组内，所有牛的值减去最小值的差之和。而总和为所有组的值之和，问：怎样分配，才能使得总和最小？

题解：

1.可得一个结论：尽量把值相近的牛分到同一组。所以首先需要根据值的大小对牛进行排序。然后就是一个区间划分的问题了。

2.由于n<=4e5，O（n^2）DP枚举是会超时的，所以需要利用斜率进行优化。

3.由于题目规定了每一组的个数必须大于等于T，因此需要特别处理：

1) dp值从下标为T开始求，因为1~T-1都不能构成一组，其DP没有意义。

2) 在求得dp[i]之后，不能直接把 i 放进队列中，因为 i 不一定能为i+1、i+2……等作状态转移，因为必须要满足一组个数大于等于T的要求。然而，这个还不是最重要的，如果直接把 i 放进队列，那么因为斜率优化所进行的操作：把认为比 i 劣且在队列里的元素出队了，而这些元素又是往后的状态所必须知道的。因此就出现了错误。

3) 根据2) 我们需要限定：在队列里的元素，必须都是往后状态所能够转移的，相比之下只是优劣问题而已。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+7;
const int MAXM = 1e5+10;
const int MAXN = 4e5+10;

LL val[MAXN], sum[MAXN], dp[MAXN];
int q[MAXN], head, tail;

LL getUp(int j, int k)
{
    return (dp[j]-sum[j]) - (dp[k]-sum[k]);
}

LL getDown(int j, int k)
{
    return j-k;
}

LL getDp(int i, int j)
{
    return dp[j]+(sum[i]-sum[j])-1LL*(i-j)*val[i];
}

int main()
{
    int T, n;
    while(scanf("%d%d", &n,&T)!=EOF)
    {
        for(int i = 1; i<=n; i++)
            scanf("%lld", &val[i]);
        sort(val+1, val+1+n);
        reverse(val+1, val+1+n);    //降序

        sum[0] = 0;
        for(int i = 1; i<=n; i++)
            sum[i] = sum[i-1]+val[i];

//        O（n^2）的写法：
//        for(int i = T; i<=n; i++)
//        {
//            dp[i] = sum[i]-i*val[i];
//            for(int j = T; j<=i-T; j++)
//                dp[i] = min(dp[i], dp[j]+sum[i]-sum[j]-1LL*(i-j)*val[i]);
//        }

        head = tail = 0;
        dp[0] = 0;
        q[tail++] = 0;
        for(int i = T; i<=n; i++)   //从T开始，因为前面的都无效
        {
            while(head+1<tail && getUp(q[head+1],q[head])<=
                  -1LL*getDown(q[head+1],q[head])*val[i]) head++;
            dp[i] = getDp(i, q[head]);

            int j = i-T+1;  //加入对从下一个开始有效的状态，而i-T+1对i+1、i+2……有效
            if(j<T) continue;   //只有j>=T, j才有效，能转移状态
            while(head+1<tail && 1LL*getUp(j, q[tail-1])*getDown(q[tail-1],q[tail-2])<=
                  1LL*getUp(q[tail-1],q[tail-2])*getDown(j, q[tail-1])) tail--;
            q[tail++] = j;
        }
        printf("%I64d
", dp[n]);
    }
}

错误写法：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+7;
const int MAXM = 1e5+10;
const int MAXN = 1e3+10;

int val[MAXN], sum[MAXN], dp[MAXN];
int q[MAXN], head, tail;

int getUp(int i, int j)
{
    return dp[i] - dp[j];
}

int getDown(int i, int j)
{
    return sum[i] - sum[j];
}

int getDp(int i, int j)
{
    return dp[j] + (sum[i]-sum[j]+10)*val[i];
}

int main()
{
    int T, n;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        sum[0] = 0;
        for(int i = 1; i<=n; i++)
            scanf("%d%d", &sum[i],&val[i]), sum[i] += sum[i-1];

        dp[0] = 0;
        head = tail = 0;
        q[tail++] = 0;
        for(int i = 1; i<=n; i++)
        {
            while(head+1<tail && getUp(q[head+1],q[head])<=getDown(q[head+1],q[head])*val[i]) head++;
            dp[i] = getDp(i, q[head]);
            /*
                直接把i加进去为何错误？因为i的存在不能为i+1的转移作贡献，本来放着没什么关系的，
                关键是i加进去的时候，还可能会把前面的去掉，这样就有可能把能为i+1转移的去掉了。
                所以，加进队列的应该是那些能为往后所有状态转移的。
            */
            while(head+1<tail && getUp(i, q[tail-1])*getDown(q[tail-1],q[tail-2])<=
                  getUp(q[tail-1],q[tail-2])*getDown(i, q[tail-1]))   tail--;
            q[tail++] = i;
        }
        printf("%d
", dp[n]);
    }
}