首页 > 代码库 > 【HDOJ】1421 搬寝室
【HDOJ】1421 搬寝室
DP。这题都能TLE,发现memset有时居然比for还要慢。
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 #define MAXN 2005 6 #define INF 0x3fffffff 7 int dp[MAXN][MAXN]; 8 int buf[MAXN]; 9 int deg[MAXN]; 10 11 int mymin(int a, int b) { 12 return (a<b) ? a:b; 13 } 14 15 int comp(const void *a, const void *b) { 16 return *(int *)a - *(int *)b; 17 } 18 19 int main() { 20 int n, m, k; 21 int i, j; 22 23 while (scanf("%d %d", &n, &k) != EOF) { 24 for (i=1; i<=n; ++i) 25 scanf("%d", &buf[i]); 26 qsort(buf+1, n, sizeof(int), comp); 27 m = 1; 28 for (i=2; i<=n; ++i) 29 deg[m++] = (buf[i]-buf[i-1])*(buf[i]-buf[i-1]); 30 31 for (i=0; i<=n; ++i) { 32 dp[i][0] = 0; 33 for (j=1; j<=k; ++j) { 34 dp[i][j] = INF; 35 } 36 } 37 38 for (i=2; i<=n; ++i) { 39 for (j=1; j+j<=i; ++j) { 40 dp[i][j] = mymin(dp[i-2][j-1]+deg[i-1], dp[i-1][j]); 41 } 42 } 43 printf("%d\n", dp[n][k]); 44 } 45 46 return 0; 47 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。