HDU 3480 Division 斜率优化DP

题意：现在有N个元素的集合S。把集合S划分成M个子集，每个子集的花费为集合中最大和最小元素的差的平方。
求如何划分，才能总的代价最小。
思路：首先要注意到，因为集合中的元素具有无序性，我们只需知道集合中最大和最小的元素就能算出代价，也能把集合划分出来。
所以，我们把所有元素进行排序，这样，最小的元素和最大的元素的位置就是已知的了。
定义：dp[i][j]将前j个元素划分成i个子集得到的最小花费和。
则:
dp[i][j]=min(dp[i−1][k]+(a j −a k+1 ) 2 )，i≤k≤N 
初始条件
dp[1][j]=(a j −a 1 ) 2  
但是这样的复杂度是 Θ(MN 2 )  ，会超时。
注意到出现了平方的形式，且 a i   有递增的性质，这启发我们可以尝试一下是否能斜率优化。
将上面的式子变形：
dp[i][j]=min(dp[i−1][k]+a 2 k+1 −2a j a k+1 )+a 2 j  
假设t < k < j，如果k比t在j更优，则有
dp[i−1][k]+a 2 k+1 −2a j a k+1 ≤dp[i−1][t]+a 2 t+1 −2a j a t+1  
变形得：
(dp[i−1][k]+a 2 k+1 )−(dp[i−1][t]+a 2 t+1 )a k+1 −a t+1  ≤2a j  
令 g(t,k)=(dp[i−1][k]+a 2 k+1 )−(dp[i−1][t]+a 2 t+1 )a k+1 −a t+1   
则
g(t,k)≤2a j  
同样，我们可以证明
1. g(t,k)≤2a j ≤2a l ,l≥j  。
2.如果 g(t,k)≥g(k,j)  ,k一定不是最优解。
上面的证明说明，我们能用单调队列来优化寻找最优解的过程。
代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 10010;
const int MAXM = 5010;

int a[MAXN];
int dp[MAXM][MAXN];
int N, M;
int q[MAXN];
int head, tail;

int main()
{
int T;
    scanf("%d", &T);
int iCase = 0;
while (T--)
    {
        iCase++;
        scanf("%d%d", &N, &M);
for (int i = 1; i <= N; i++)
            scanf("%d", &a[i]);
sort(a + 1, a + N + 1);

for (int i = 1; i <= N; i++)
            dp[1][i] = (a[i] - a[1])*(a[i] - a[1]);

for (int i = 2; i <= M; i++)
        {
            head = tail = 0;
q[tail++] = i - 1;
for (int j = i; j <= N; j++)
            {
while (head + 1 < tail)
                {
int p1 = q[head];
int p2 = q[head + 1];
int x1 = a[p1 + 1];
int x2 = a[p2 + 1];
int y1 = dp[i - 1][p1] + x1*x1;
int y2 = dp[i - 1][p2] + x2*x2;
if ((y2 - y1) <= 2 * a[j] * (x2 - x1))head++;
else break;
                }
int k = q[head];
                dp[i][j] = dp[i - 1][k] + (a[j] - a[k + 1])*(a[j] - a[k + 1]);
while (head + 1 < tail)
                {
int p1 = q[tail - 2];
int p2 = q[tail - 1];
int p3 = j;
int x1 = a[p1 + 1];
int x2 = a[p2 + 1];
int x3 = a[p3 + 1];
int y1 = dp[i - 1][p1] + x1*x1;
int y2 = dp[i - 1][p2] + x2*x2;
int y3 = dp[i - 1][j] + x3*x3;
if ((y3 - y2)*(x2 - x1) <= (y2 - y1)*(x3 - x2))tail--;
else break;
                }
q[tail++] = j;
            }
        }
printf("Case %d: %d\n", iCase, dp[M][N]);
    }
return 0;
}