HDU 1421 搬寝室

点我看题目

题意 ：中文题。

思路 ：DP题，因为一开始没想到该怎么找两个两个的，所以一开始没有思路，后来别人给讲了才知道。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std ;

int dp[2010][1010] ;
int a[2014] ;

int main()
{
    int n, k ;
    while(~scanf("%d %d",&n,&k))
    {
        for(int i = 1 ; i <= n ; i++)
        scanf("%d",&a[i]) ;
        sort(a+1,a+1+n) ;
        dp[0][0] = 0 ;
        for(int i = 2 ; i <= n ; i++)
        {
            dp[i][0] = 0 ;
            for(int j = 1 ; j <= i/2 ; j++)
            {
                if(i-1 >= j * 2)
                dp[i][j] = min(dp[i-1][j],dp[i-2][j-1] + (a[i-1]-a[i]) * (a[i-1]-a[i])) ;
                else
                 dp[i][j] = dp[i-2][j-1] + (a[i-1]-a[i])*(a[i-1]-a[i]);
            }
        }
        printf("%d
",dp[n][k]) ;
    }
    return 0 ;
}