当前位置: 代码迷 >> 综合 >> HDU1421 搬寝室(DP)
  详细解决方案

HDU1421 搬寝室(DP)

热度:32   发布时间:2024-01-16 13:38:22.0

题意:

中文题不解释。

要点:

要在n个中选k对,使每两个之差的平方和最小,可以用dp[i][j]来表示i个数中选了j对的最小值,以当前的第i个数来判断,如果不选这个数,说明就是前一个数的值,dp[i][j]=dp[i-1][j];如果选这个数,说明它前面的数也要被选,dp[i][j]=dp[i-2][j-1]+(val[i]-val[i-1])^2。状态转移方程就是:dp[i][j] = min(dp[i - 2][j - 1] + (val[i] - val[i - 1])*(val[i] - val[i - 1]), dp[i - 1][j]),边界条件是dp[0][j]=dp][i][0]=0,其他的赋值为一个较大值。


17420080 2016-07-02 10:48:53 Accepted 1421 187MS 9272K 649B G++ seasonal
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int val[2005], dp[2005][1005];int main()
{int n,k,i,j;while (scanf("%d%d", &n,&k) != EOF){for (i = 1; i <= n; i++)scanf("%d", &val[i]);sort(val+1, val + n+1);for (i = 1; i <= n; i++)for (j = 1; j <= k; j++)dp[i][j] = 0xfffffff;for (i = 0; i <= n; i++)dp[i][0] = 0;for (j = 0; j <= k; j++)dp[0][j] = 0;for (i = 2; i <= n; i++)for (j = 1; 2*j <= i; j++)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;
}


  相关解决方案