misschuer

常用鏈接

統計

隨筆 - 61
文章 - 1
評論 - 18
引用 - 0

積分與排名

積分 - 24596
排名 - 731

百事通

hao123
WPL
杭電
松松
星和

hdu 1421 搬寢室詳解

#include <iostream>
2

#include <algorithm>
3

using namespace std;
4

int cmp( const void *a , const void *b )
6

{
7

return *(int *) a - *(int *) b;
8

}
9

int dp[ 2000 ][ 1000 ];
11

int main()
13

{
14

int n , k , i , j;
16

int a[ 2000 ];
18

while (scanf ("%d %d" , &n , &k) != EOF)
20

{
21

for(i = 1 ; i <= n ; ++ i)
22

scanf ("%d" , &a[ i ]);
24

qsort (a , n + 1 , sizeof (a[ 1 ]) , cmp);
26

for(i = 1 ; i < n ; ++ i)
28

a[ i ] = (a[i + 1] - a[ i ]) * (a[i + 1] - a[ i ]);
30

for(i = 0 ; i <= n ; ++ i)
33

for(j = 1 ; j <= k ; ++ j)
35

dp[ i ][ j ] = 100000000;
37

for(i = 0; i <= n; ++ i)
41

dp[ i ][ 0 ] = 0;
43

for(i = 2 ; i <= n ; ++ i)
47

for(j = 1; 2 * j <= i ; ++ j )
49

{
50

dp[ i ][ j ] = dp[ i - 1 ][ j ];
51

if(dp[ i ][ j ] > dp[ i - 2 ][ j - 1] + a[ i - 1] )
53

dp[ i ][ j ] = dp[ i - 2 ][ j - 1] + a[ i - 1];
55

}
56

printf ("%d\n" , dp[ n ][ k ]);
58

}
59

return 23;
61

}

posted on 2009-04-18 15:37 此最相思閱讀(856) 評論(3) 編輯收藏引用所屬分類: dp

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: hdu 1500 Chopsticks hdu 1421 搬寢室詳解

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# re: 搬寢室詳解 2009-04-18 22:01 Sunshine Alike

# re: 搬寢室詳解 2009-04-19 10:06 GY

# re: hdu 1421 搬寢室 2009-04-19 12:20 yangyin

misschuer

導航

公告

留言簿

隨筆分類

文章分類

隨筆檔案

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

積分與排名

百事通

最新評論

hdu 1421 搬寢室詳解

評論

misschuer

導航

公告

留言簿

隨筆分類

文章分類

隨筆檔案

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

積分與排名

百事通

最新評論

hdu 1421 搬寢室 詳解

評論

# re: 搬寢室 詳解 2009-04-18 22:01 Sunshine Alike

# re: 搬寢室 詳解 2009-04-19 10:06 GY

# re: hdu 1421 搬寢室 2009-04-19 12:20 yangyin

hdu 1421 搬寢室詳解

# re: 搬寢室詳解 2009-04-18 22:01 Sunshine Alike

# re: 搬寢室詳解 2009-04-19 10:06 GY