hdu 1421 클래식 dp

1675 단어
#include<stdio.h>
#include<stdlib.h>
#define N 2001
#define inf 0x3fffffff
int a[N],dp[N][N];
int Min(int v,int vv) {
return v>vv?vv:v;
}
int cmp(const void *a,const void *b) {
return *(int *)a-*(int *)b;
}
int main() {
   int n,k,i,j;
   while(scanf("%d%d",&n,&k)!=EOF) {
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    qsort(a+1,n,sizeof(a[0]),cmp);
    for(i=1;i<=n;i++)
if((i+1)%2==0)
         dp[i][(i+1)/2]=inf;//                   
    for(i=0;i<=n;i++)
        dp[i][0]=0;
    for(i=2;i<=n;i++)
        for(j=1;j*2<=i;j++)
        dp[i][j]=Min(dp[i-1][j],dp[i-2][j-1]+(a[i-1]-a[i])*(a[i-1]-a[i]));
        printf("%d
",dp[n][k]); } return 0;} /* , !!!!, #include <iostream> #include <algorithm> using namespace std ; int dp[2001][1001],w[2001] ; bool cmp(int a,int b) { return a<b ; } int main() { int n,k ; while(~scanf("%d%d",&n,&k)) { for(int i=1;i<=n;i++) scanf("%d",&w[i]) ; sort(w+1,w+n+1,cmp) ; for(i=0;i<=n;i++) dp[i][0]=0;// i,0 0 for(int i=2;i<=n;i++) for(int j=1;(j<<1)<=i;j++) { if(i==(j<<1))// i dp[i-1][j] i-1<j*2 dp[i][j]=dp[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]) ; else // , i=5,j=2 i=4,j=2 , dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1])) ; } printf("%d
",dp[n][k]) ; } return 0 ; } */

좋은 웹페이지 즐겨찾기