程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3480 Division （斜率優化）

hdu 3480 Division （斜率優化）

編輯：C++入門知識

Division

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 999999/400000 K (Java/Others) Total Submission(s): 2676 Accepted Submission(s): 1056

Problem Description 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 cZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc3Qgb2YgZWFjaCBzdWJzZXQgaXMgbWluaW1hbC4gCiAKPGJyPgpJbnB1dApUaGUgaW5wdXQgY29udGFpbnMgbXVsdGlwbGUgdGVzdCBjYXNlcy48YnI+CkluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCB0aGVyZaGvcyBhbiBpbnRlZ2VyIFQgd2hpY2ggaXMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBUaGVuIHRoZSBkZXNjcmlwdGlvbiBvZiBUIHRlc3QgY2FzZXMgd2lsbCBiZSBnaXZlbi4KPGJyPgpGb3IgYW55IHRlc3QgY2FzZSwgdGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gKKHcIDEwLDAwMCkgYW5kIE0gKKHcIDUsMDAwKS4gTiBpcyB0aGUgbnVtYmVyIG9mIGVsZW1lbnRzIGluIFMgKG1heSBiZSBkdXBsaWNhdGVkKS4gTSBpcyB0aGUgbnVtYmVyIG9mIHN1YnNldHMgdGhhdCB3ZSB3YW50IHRvIGdldC4gSW4gdGhlIG5leHQgbGluZSwgdGhlcmUgd2lsbCBiZSBOIGludGVnZXJzIGdpdmluZyBzZXQgUy48YnI+Cjxicj4KCiAKPGJyPgpPdXRwdXQKRm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyBleGFjdGx5IG9uZSBpbnRlZ2VyLCB0aGUgbWluaW1hbCB0b3RhbCBjb3N0LiBUYWtlIGEgbG9vayBhdCB0aGUgc2FtcGxlIG91dHB1dCBmb3IgZm9ybWF0Ljxicj4KPGJyPgoKIAo8YnI+ClNhbXBsZSBJbnB1dAoKPHByZSBjbGFzcz0="brush:java;">2 3 2 1 2 4 4 2 4 7 10 1
Sample Output

Case 1: 1
Case 2: 18


HintThe answer will fit into a 32-bit signed integer.

Source 2010 ACM-ICPC Multi-University Training Contest（5）——Host by BJTU
題意：將含有N個元素的一個集合分成M個子集，使得每個子集的最大值與最小值平方差的和最小。

思路：可以想到貪心將元素從小到大排序，很快可以得出dp[i][j]-前i個子集分j個元素的最小花費， dp方程 dp[i][j]=dp[i-1][k]+(a[j]-a[k+1])；但是需要三重循環，時間復雜度接受不了，所以需要優化，這題斜率優化和四邊形不等式都可以，我采用的是剛學習的斜率優化。設k1 代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define maxn 205
#define MAXN 100005
#define mod 100000000
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,m,ans,cnt,tot,flag;
int a[10005],dp[2][10005];
int q[10005];

int sqr(int x)
{
    return x*x;
}
int get(int i,int k)
{
    return dp[i][k]+a[k+1]*a[k+1];
}
void solve()
{
    int i,j,t,dx1,dy1,dx2,dy2,k1,k2,turn=0;
    int head,tail;
    sort(a+1,a+n+1);
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(i=1; i<=m; i++)
    {
        head=0; tail=-1;
        q[++tail]=i-1;
        for(j=i; j<=n; j++)
        {
            while(head