题目：http://acm.hdu.edu.cn/showproblem.php?pid=1421
对每相邻的一对取或者不取
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 |
#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <stack>#include <queue>#include <vector>#include <map>#include <string>#include <iostream>using
namespace std;const
int INF=0xfffffff;int
Min(int
a,int b){ return
a>b?b:a;}int
a[2222];int
dp[2222][1111];int
main(){ int
n,k; while(scanf("%d%d",&n,&k)!=EOF){ for(int
i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); for(int
i=1;i<=n;i++) for(int
j=1;j<=k;j++) dp[i][j]=INF; for(int
i=0;i<=n;i++) dp[i][0]=0; for(int
i=1;i<=n;i++){ for(int
j=0;j<=i/2;j++){ dp[i][j]=Min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1])); } } printf("%d\n",dp[n][k]); } return
0;} |
原文：http://www.cnblogs.com/yigexigua/p/3782008.html