[条件限制动态规划] 佳佳的筷子

佳佳的筷子

题目描述

佳佳与常人不同，吃饭用三只筷子，两根短的加一根比较长的。两只短的筷子的长度应该尽可能接近，但是最长的那根长度是无所谓的。如果一套筷子的长度分别是a,b,c(a<=b<=c),则用(a-b)*(a-b)的值表示这套筷子的质量，这个值越小，这套筷子的质量越高。
佳佳请朋友吃饭，并准备为每人准备一套这种特殊的筷子。佳佳有n(n<=5000)只筷子,他希望找到一种办法搭配好k套筷子，使得这些筷子的质量之和最小。

关于输入

第一行是两个整数n和k(n<=5000,3*k<=n)
第二行是n个整数表示筷子的长度

关于输出

输出一个整数,表示筷子质量和的最小值

例子输入

5 1
1 3 4 7 10

例子输出

1

提示信息

从小到大排序后从后向前递推

解题分析

本题明显地需要动态规划来寻找最佳的解决方案，我们不妨令dp[i][j]，表示取i只筷子，拿j套筷子质量和的最小值。拿了两只筷子后，必须还要一只比这两只筷子都长的筷子，所以逆推相对来说较为轻松，并且相邻两数平方和最小，故我们先将筷子按从大到小排序，然后再规定初始条件，对于那些筷子数不足以凑足需要的筷子套数的情况，我们将其状态置为一个较大的数，这样就可以防止错取，对于取0套筷子的情况，因为一套筷子也没有，故质量和置为0。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;

int chopsticks[5005];
int dp[5005][5005/3+1];

int main(){
    int n,k; cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>chopsticks[i];
    }
    sort(chopsticks+1,chopsticks+n+1,greater<int>());
    for(int i=1;i<=k;i++){
        dp[i*3-1][i]=1e6;
    }
    dp[3][1]=(chopsticks[3]-chopsticks[2])*(chopsticks[3]-chopsticks[2]);
    for(int j=1;j<=k;j++)
        for(int i=3*j;i<=n;i++){
            dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(chopsticks[i]-chopsticks[i-1])*(chopsticks[i]-chopsticks[i-1]));
        }
    cout<<dp[n][k]<<endl;
    return 0;
}