HDU 3480 DP+斜率優化

題意：給你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][1] = (a[i] - a[1]) * (a[i] - a[1]) ;  
    }  
    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 ;  
}