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 ;

}

巴特西

HDU 3480 DP+斜率优化

最新文章

热门文章