dp斜率优化 Hdu 3480 Division 题解

累加器传送门：

：http://blog.csdn.net/NOIAu/article/details/71775000

---

题目传送门：

https://vjudge.net/problem/HDU-3480

---

题目：

Little D is really interested in the theorem of sets recently. There’s a problem that confused him a long time.
Let T be a set of integers. Let the MIN be the minimum integer in T and MAX be the maximum, then the cost of set T if defined as (MAX – MIN)^2. Now given an integer set S, we want to find out M subsets S1, S2, …, SM of S, such that

---

and the total cost of each subset is minimal.

输入：

The input contains multiple test cases.
In the first line of the input there’s an integer T which is the number of test cases. Then the description of T test cases will be given.
For any test case, the first line contains two integers N (≤ 10,000) and M (≤ 5,000). N is the number of elements in S (may be duplicated). M is the number of subsets that we want to get. In the next line, there will be N integers giving set S.

---

输出：

For each test case, output one line containing exactly one integer, the minimal total cost. Take a look at the sample output for format.

---

样例输入：

2
3 2
1 2 4
4 2
4 7 10 1

---

样例输出：

Case 1: 1
Case 2: 18

---

先排序，然后

用dp[i][j]表示前j个数，分为i段的最优值

容易写出：
dp[i][j]=min{dp[i-1][k]+cost[k+1][j]}
由于数据已经有序，自然cost[k+1][j]的值应该等于（a[j]-a[k+1]）^2
所以写出转移方程
dp[i][j]=dp[i-1][k]+a[k+1]^2-2 *a[j] *a[k+1]+a[j]^2

令b=dp[i][j]

y=dp[i-1][k]+a[k+1]^2

k=2*a[j]

x=a[k+1]

二维的斜率优化就可以了
代码如下

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 10000+10

using namespace std;

int cn;
int a[MAXN];
int q[MAXN];
int head,tail;
int n,m;
int dp[MAXN][MAXN];
int T;

void init(){
    scanf("%d%d",&n,&m);
for(register int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
}

void dpp(){ 
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 y1=dp[i-1][q[head]]+a[q[head]+1]*a[q[head]+1];
int y2=dp[i-1][q[head+1]]+a[q[head+1]+1]*a[q[head+1]+1];
int x1=a[q[head]+1];
int x2=a[q[head+1]+1];
if(y1-2*a[j]*x1>=y2-2*a[j]*x2)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 x1=a[j+1]-a[q[tail-1]+1];
int y1=dp[i-1][j]+a[j+1]*a[j+1]-(dp[i-1][q[tail-1]]+a[q[tail-1]+1]*a[q[tail-1]+1]);
int x2=a[q[tail-1]+1]-a[q[tail-2]+1];
int y2=dp[i-1][q[tail-1]]+a[q[tail-1]+1]*a[q[tail-1]+1]-(dp[i-1][q[tail-2]]+a[q[tail-2]+1]*a[q[tail-2]+1]);
if(x1*y2-x2*y1>=0)tail--;
else break;
            }
q[tail++]=j;
        }
    }
printf("Case %d: %d\n",++cn,dp[m][n]);
}

int main(){
    scanf("%d",&T);
while(T--){
        init();
        dpp();
    }
}