题目来源：《算法艺术与信息学竞赛》Page145
题目1.5.12
题目提交方式：uva10271
汗，今天发现我的代码在uva上不能ac，那天比赛数据弱，被我骗过去了～～题目描述：
n个数中选k＋8组共（k＋8）×3个数，每组数三个，每组数中较小的两个数Ai，Bi，其代表的值为（Ai－Bi)^2,另所有组的值的和最小。
解题思路：
(来自OIBH的思路）首先，我们直观的猜测：任意一副筷子中A和B一定是长度相邻的两只筷子。证明如下：对于某副筷子(A1,B1,C1)和另一副筷子(A2,B2,C2)，如果A1<=A2<=B1<=B2，那么交换一下筷子重新组合成(A1,A2,C1)和(B1,B2,C2)质量和会更优。对于某副筷子(A,B,C)和闲置的筷子D，如果A<=D<=B，那么交换一下重新组合成(A,D,C)质量和也会更优。
这样，我们得到了一个线性结构，只需要从左往右或从后往左递推。在本题中，由于第3根筷子比另2根长，所以我们从长筷子往短筷子递推。在递推之前，首先将N只筷子从小到大排序，Li是第i只筷子的长度。
用d[i,j]表示用i..n的单只筷子组成j副筷子的最小质量值之和，则当且仅当n-i+1>=3j的时候状态是合法的。请读者自己写出状态转移方程。
这个题目比较难，我是看了上面的思路写的，状态转移方程为:
f[i][j]
= MIN( f[i-1][j], f[i+2][j-1] + (a[i+1]-a[i]) * (a[i+1]-a[i]) )//对应与上面思路，
由于数据比较大，实现时用到滚动数组。
题目代码：
1 /*********************************************************************
2 Author: littlekid
3 Created Time: 2008-2-16 13:35:08
4 Problem Source:
5 Description:
6 ********************************************************************/
7 # include <iostream>
8 using namespace std;
9
10 # define N 5005
11
12 const int maxint = 0xfffffff;
13
14 int k, n;
15 int a[ N ];
16 int f[2][N] = { 0 };
17 int ans;
18
19 void init()
20 {
21 scanf("%d %d", &k, &n);
22 for (int i = 0; i < n; i ++)
23 {
24 scanf("%d", &a[i]);
25 }
26 k+=8;
27 }
28
29 int cmp(const void *a, const void *b)
30 {
31 return (*(int *)a-*(int *)b);
32 }
33
34 int MIN(int a, int b)
35 {
36 return a > b ? b : a;
37 }
38
39 void dp()
40 {
41 qsort(a, n, sizeof(a[0]), cmp);
42 //cout << a[0] << endl; ////
43 for (int i = n; i > 0; i --) a[i] = a[i-1];//
44
45 int now = 0, pre = 1;
46
47 for (int j = 1; j <= k; ++j)
48 {
49 if (now == 1)
50 {
51 now = 0, pre = 1;
52 }
53 else
54 {
55 now = 1, pre = 0;
56 }
57 for (int i = j * 2; i <= n; ++i)
58 {
59 if (i > j * 2)
60 f[now][i] = f[now][i - 1];
61 else
62 f[now][i] = maxint;
63 if ((n - i) > (k - j) * 3)
64 f[now][i] = MIN(f[now][i], f[pre][i - 2] + (a[i] - a[i - 1]) * (a[i] - a[i - 1]));
65 }
66 }
67 ans = f[now][n];
68 }
69
70 void output()
71 {
72 printf("%d\n", ans);
73 }
74
75 int main()
76 {
77 int T; scanf("%d", &T);
78 while (T --)
79 {
80 init();
81 dp();
82 output();
83 }
84 return 0;
85 }
86
87
posted on 2008-02-16 20:32
R2 阅读(2335)
评论(3) 编辑 收藏 引用 所属分类:
Problem Solving