題目來源：《算法藝術與信息學競賽》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 閱讀(2429)
評論(3) 編輯 收藏 引用 所屬分類:
Problem Solving