题目链接:HDU 1421 搬寝室
中文题。
dp[i][j] 的意义是:前i件物品取2*j 件的最小疲劳值
先从小到大排序。
当j==2*i ,dp[i][j]=dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]);
当j>2*i,dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));
AC代码:
#include<stdio.h>#include<string.h>#include<algorithm>#define LL __int64using namespace std;const LL maxn=2200;LL dp[maxn][1200+5];//选前i件物品还可拿j对物品的最小疲劳LL a[maxn];int main(){LL i,j;LL n,k;while(scanf("%I64d%I64d",&n,&k)!=EOF){memset(dp,0,sizeof dp);for(i=1;i<=n;i++){scanf("%I64d",&a[i]);}sort(a+1,a+n+1);for(i=1;i<=k;i++){for(j=2;j<=n;j++){if(j==2*i)dp[j][i]=dp[j-2][i-1]+(a[j]-a[j-1])*(a[j]-a[j-1]);if(j>2*i)dp[j][i]=min(dp[j-1][i],dp[j-2][i-1]+(a[j]-a[j-1])*(a[j]-a[j-1]));//printf("%I64d %I64d %I64d\n",j,i,dp[j][i]);}}printf("%I64d\n",dp[n][k]);}return 0;}/*2 11 35 21 3 4 6 97 21 3 4 8 9 10 125 21 4 6 */
,片的时光如浮云般流过,我们的青春单薄的穿梭在蓝天之上。