题意：给你n个数字，然后叫你从这些数字中选出m堆，使得每一堆的总和最小，一堆的总和就是这一堆中最大值减去最小值的平方，最后要使得所有堆加起来的总和最小。
思路：对这些数字排序之后，很容易想到DP解法，用dp[i][j]表示数字i现在在第j堆，那么转移方程就是dp[i][j] = min（dp[i][j] , dp[k][j - 1] + （a[i] - a[k + 1]） ^ 2）。因为已经排序，所以这一堆中的最大最小值其实就是a[i]和a[k + 1].所以用DP可解。
但是注意到这实际上是需要3重循环的，而且N和M分别为10 ^ 4和5 * 10 ^ 3,所以会TLE.
其实看到转移方程后面的部分，我们就应该能想到斜率优化的方法。
假设k < l < i,我们要使得k的决策优于l,那么也就是dp[k][j - 1] + （a[i] - a[k + 1]） ^ 2 < dp[l][j - 1] + （a[i] - a[l + 1]） ^ 2 .
化简得（dp[k][j - 1] + a[k + 1] ^ 2 - （dp[l][j - 1] + a[l + 1] ^ 2）） / （2 * （a[k + 1 ] - a[l + 1]）） < a[i] .
也就是说符合上述斜率要求的k,是优于l的。
我们用g（k ,l ）表示k的决策优于l.
那么我们每次更新 dp[i][j]的值的时候，只需要取出最优的决策即可，所以这一维就是O（1） .
进一步说，在第一个while 中，如果这时候队列里有两个元素，qe[l + 1] 和qe[l].如果这时候g（qe[l + 1] , qe[l]）成立，那么这时候qe[l]就不需要再计算了，因为qe[l + 1]的决策比他更优，所以我们只需要找出最优的决策，更新一次即可。
同样的，假设k < l < i .如果g（i , l ） < g（l , k），那么此时l是可以被优化掉的。因为他不可能是最优解。这就是第二个while的作用。
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Max 2505
#define FI first
#define SE second
#define ll long long
#define PI acos（-1.0）
#define inf 0x3fffffff
#define LL（x） （ x 《 1 ）
#define bug puts（"here"）
#define PII pair<int,int>
#define RR（x） （ x 《 1 | 1 ）
#define mp（a,b） make_pair（a,b）
#define mem（a,b） memset（a,b,sizeof（a））
#define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
using namespace std;
#define N 11111
#define M 5555
int dp[N][M] ;
int a[N] ;
int getU（int j ,int k ,int z）{
return dp[k][j - 1] + a[k + 1] * a[k + 1] - （dp[z][j - 1] + a[z + 1] * a[z + 1]） ;
}
int getD（int k , int z）{
return 2 * （a[k + 1] - a[z + 1]） ;
}
int getDP（int i , int j ,int k）{
return dp[k][j - 1] + （a[i] - a[k + 1]） * （a[i] - a[k + 1]） ;
}
int qe[N * 10] ;
void solve（）{
int n , m ;
cin 》 n 》 m ;
for （int i = 1 ; i <= n ; i ++ ）cin 》 a[i] ;
sort（a + 1 , a + n + 1 ） ;
for （int i = 0 ; i <= n ; i ++ ）{
for （int j = 0 ; j <= m ; j ++ ）
dp[i][j] = inf ;
dp[i] = （a[i] - a ） * （a[i] - a ） ;
}
dp[0][0] = 0 ;
for （int j = 1 ; j <= m ; j ++ ）{
int l = 0 , r = 0 ;
qe[r ++ ] = 0 ;
for （int i = 1 ; i <= n ; i ++ ）{
while（l + 1 < r && getU（j , qe[l + 1] , qe[l]） <= a[i] * getD（qe[l + 1] ,qe[l]））l ++ ;
dp[i][j] = getDP（i , j , qe[l]） ;
while（l + 1 < r && getU（j , i , qe[r - 1]） * getD（qe[r - 1] , qe[r - 2]） <=
getU（j , qe[r - 1] , qe[r - 2]） * getD（i , qe[r - 1]））r -- ;
qe[r ++ ] = i ;
}
}
cout 《 dp[n][m] 《 endl;
}
int main（） {
int ca = 0 ;
int t ; cin 》 t ; while（t -- ）{
printf（"Case %d: ",++ca） ;
solve（） ;
}
return 0 ;
} |