HDU 1421 DP

 

那么想想dp[i][j]是怎么来的，

 

（1）i==j*2    dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1])

 

（2）i>j*2       dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]))

 

注意long long 会超时 多组输入

 

很奇怪的是 我数组开了2002*2002  WA了多次 开大一些  AC...无语...

 

贴代码：

 
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
#define N 2050  
#define ll int  
  
ll dp[N][N];  
ll a[N];  
  
int main()  
{  
    ll n,k,i,j;  
  
    while(scanf("%d%d",&n,&k)!=EOF)  
    {  
        for(i=1;i<=n;i++)  
            scanf("%d",&a[i]);  
        sort(a+1,a+n+1);  
        memset(dp,0,sizeof(dp));  
        dp[2][1]=(a[2]-a[1])*(a[2]-a[1]);  
  
        for(j=1;j<=k;j++)  
            for(i=j*2;i<=n;i++)  
            {  
                dp[i][j]=dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]);  
                if(j*2<i)  
                {  
                    dp[i][j]=min(dp[i-1][j],dp[i][j]);  
                }  
  
  
            }  
        printf("%d\n",dp[n][k]);  
    }  
  
    return 0;  
}  

 

补充：软件开发 , C++ ,