hdu 1421(dp)

题意：容易理解...

思路：假设开始算出搬了k次的最小疲劳度，然后推出搬k+1次最小的疲劳度。

代码实现：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int min1[2001],dp[2001];
int main()
{
    int n,k,i,j,a[2001],b[2001],temp,res;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        for(i=2;i<=n;i++)
            b[i]=(a[i]-a[i-1])*(a[i]-a[i-1]);
        memset(min1,0,sizeof(min1));
        for(i=1;i<=k;i++)
        {
            for(j=2*i;j<=n;j++)
            {
                dp[j]=min1[j]+b[j];
                if(j>=2*(i+1))
                    min1[j]=temp;
                if(j==2*i)
                    temp=dp[j];
                else if(temp>dp[j-1])
                    temp=dp[j-1];
            }
        }
        res=100000000;
        for(i=2*k;i<=n;i++)
            if(res>dp[i])
                res=dp[i];
        printf("%d
",res);
    }
    return 0;
}