hdu 2078

这题我一看就想到了DP，然后也按着DP做了，然后一次就AC了

但是，我从网上找了下别人的思路，又有种想哭的感觉

别人只是找到最小的算一下平方差，就过了，仔细考虑了一下，也对

两个数的平方差>与中间任意几个数的平方差的和

在此我是不是应该反思一下，我的DP代码是否是真的对了呢

#include 
#include 
#include 
#include 
using namespace std;
int main()
{
    int i,cas,n,m,ans;
    int a[45];
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        for(i=0;i 
 
#include 
#include 
#include 
#include 
using namespace std;
bool cmp(const int &a,const int &b)
{
    return a>b 1:0;
}
int main()
{
    int i,j,cas,n,m,ans;
    int dp[45][105],a[45][45],c[45];
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        for(i=1;i<=n;i++)
        scanf("%d",&c[i]);
        sort(c+1,c+n+1,cmp);
        c[0]=100;
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=i;j++)
            {
                a[i][j]=(c[i]-c[j])*(c[i]-c[j]);
            }
        }
    //    printf("%d %d %d\n",a[1][0],a[2][0],a[0][0]);
        ans=0;
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(i==1) dp[i][j]=a[j][0];
                else
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+a[j][j-1]);
                ans=max(ans,dp[i][j]);
            }
        }
        printf("%d\n",ans);

    }
    return 0;
}