hdu 1421 搬寝室，dp

绝地灬酷狼 2022-07-31 08:28 155阅读 0赞

题意：

在n个物品里面选取k对物品，使这k对物品的平方差之和最小。

分析：

一道典型的dp题目。

dp\[i\]\[j\]表示的是在前i个物品里面选取j对的品方差之和，其中i大于等于j\*2

我们对，物品排序之和会发现，由于是平方差之和，那么一个数字一般只会和他前面的一个数字或者后面的数字组合。

这样我们来想递推方程的时候会简单很多的。

dp\[i\]\[j\]  有两种方式可以得到，一种是这j对物品中包括第i个物品，一种是不包括，包括i的话，那么i物品一定会和i-1物品配对，然后加上在前i-2个物品中选取j-1对，

这时就是dp\[i-2\]\[j-1\]+(val\[i\]-val\[i-1\])\*(val\[i\]-val\[i-1\])；

不包括i的话，那么就直接是dp\[i-1\]\[j\]，选取两者中的较小值就可以了的。

但我们应该注意到，若i是偶数并且j\*2正好等于i的话，那么就没有dp\[i-1\]\[j\],这时候直接等于dp\[i-2\]\[j-1\]+(val\[i\]-val\[i-1\])\*(val\[i\]-val\[i-1\])。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <string>
    using namespace std;
    
    #define size 2005
    
    int dp[size][1005];
    int val[size] ;
    
    int main()
    {
    	int n,k;
    	while (scanf("%d%d",&n,&k)!=EOF)
    	{
    		val[0] = 0;
    		for(int i = 1 ; i <= n ; i++)
            {
                scanf("%d",&val[i]);
            }
    		sort(val+1,val+n+1);
    		memset(dp,0,sizeof(dp));
    		for (int i = 2 ; i <= n ; i++)
    		{
    			for (int j = 1 ; j*2 <= i ; j++)
                {
                    if(j*2==i) dp[i][j] = dp[i-2][j-1]+(val[i]-val[i-1])*(val[i]-val[i-1]);
                    else  dp[i][j] = min(dp[i-1][j],dp[i-2][j-1]+(val[i]-val[i-1])*(val[i]-val[i-1]));
                    //dp[i][j] = min(dp[i-2][j-1]+(val[i]-val[i-1])*(val[i]-val[i-1]),dp[i-1][j]);
                }
    		}
    		printf("%d\n",dp[n][k]);
    	}
    	return 0;
    }