题目1452：搬寝室（dp题目）

题目链接：http://ac.jobdu.com/problem.php?pid=1452

详解链接：https://github.com/zpfbuaa/JobduInCPlusPlus

参考代码：

//

//  1452 搬寝室.cpp

//  Jobdu

//

//  Created by PengFei_Zheng on 24/04/2017.

//  Copyright © 2017 PengFei_Zheng. All rights reserved.

//

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <string.h>

#include <cmath>

#include <limits.h>

//#define MAX 0x7fffffff

#define MAX_SIZE 2001

#define MAX_ROW 1001

using namespace std;

int n, k;

int weight[MAX_SIZE];

long long dp[MAX_ROW][MAX_SIZE];

int main(){

    while(scanf("%d%d",&n,&k)!=EOF){

        for(int i =  ; i <= n ; i++){

            scanf("%d",&weight[i]);

        }

        sort(weight+,weight++n);

        for(int i =  ; i <= n ; i++){

            dp[][i]=;

        }

        for(int i =  ; i <= k ; i++){

            for(int j = *i ; j <= n ; j++){

                if(j>*i){

                    dp[i][j] = dp[i][j-];

                }

                else

                    dp[i][j] = INT_MAX;

                if(dp[i][j] > dp[i-][j-]+pow(weight[j]-weight[j-],)){

                    dp[i][j] = dp[i-][j-]+pow(weight[j]-weight[j-],);

                }

            }

        }

        printf("%lld\n",dp[k][n]);

    }

    return ;

}

/**************************************************************

    Problem: 1452

    User: zpfbuaa

    Language: C++

    Result: Accepted

    Time:50 ms

    Memory:17176 kb

****************************************************************/