hdu 2078

這題我一看就想到了DP，然後也按著DP做了，然後一次就AC了

但是，我從網上找了下別人的思路，又有種想哭的感覺

別人只是找到最小的算一下平方差，就過了，仔細考慮了一下，也對

兩個數的平方差>與中間任意幾個數的平方差的和

在此我是不是應該反思一下，我的DP代碼是否是真的對了呢

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
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<n;i++)
        scanf("%d",&a[i]);
        sort(a,a+n);
        ans=(100-a[0])*(100-a[0]);
        printf("%d\n",ans);
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
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;
}