May the force be with you!
posts - 52,  comments - 33,  trackbacks - 0

题目来源:《算法艺术与信息学竞赛》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 阅读(1656) 评论(3)  编辑 收藏 引用 所属分类: Problem Solving

FeedBack:
# re: 【DP】“佳佳的筷子”的解法
2010-02-19 18:49 | Lee1R
上面的状态转移方程我没有看太懂……
d[i][j]=min(d[i-1][j],d[i+2][j-1]+(a[i+1]-a[i])^2);
方程的含义应该是第i根筷子要么不使用,要么就和i+1根筷子一起使用,两根短筷子必须相邻这我知道,但是长筷子不需要考虑在状态转移方程中吗?
如果在这解答不方便,可以和我联系。QQ120501168
  回复  更多评论
  
# re: 【DP】“佳佳的筷子”的解法
2010-03-06 13:10 | R2
@Lee1R

如上所述,本解法是错的。具体解法现在已经无印象了
  回复  更多评论
  
# re: 【DP】“佳佳的筷子”的解法
2010-03-06 18:42 | Lee1R
@R2
这种解法是正确的!我后来想明白了,因为这种决策方式可以保证第三根筷子有的选!
具体看我的解题报告:
http://www.cppblog.com/rakerichard/archive/2010/02/19/108081.html
  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


你是第 free hit counter 位访客




<2010年3月>
28123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿(4)

随笔分类(54)

随笔档案(52)

文章档案(1)

ACM/ICPC

技术综合

最新随笔

搜索

  •  

积分与排名

  • 积分 - 53144
  • 排名 - 349

最新评论

阅读排行榜

评论排行榜