《快乐的蜜月》 — 编程爱好者社区

[问题的模型]
　　在数轴上有一些线段，线段具有权值。一种方案是指一组没有重叠的线段的集合，一种方案的总收益就是这些被选线段的权值和。在所有的方案中，求第k大的收益。

[问题分析]
　　该题用动态规划解。

　　先考虑k=1的情况，即每次取最大值。这题线段端点的范围较小(从1到366)，适合做阶段。设f(d)表示前d天可以达到的最大收益，Sd表示右端点在第d天的线段集合。 
 
　　(1) 如果f(d)不选取[img]http://www.chinaschool.org/aosai/lwjl/images/02-0222-01.gif[/img]中的任意线段，则f(d) = f(d-1) 
　　(2) f(d)只选择[img]http://www.chinaschool.org/aosai/lwjl/images/02-0222-01.gif[/img]中的某条线段(只能选取一条，因为
[img]http://www.chinaschool.org/aosai/lwjl/images/02-0222-01.gif[/img]中线段右端点都相同，选取多条就冲突了)。设选择线段x，其左端点为d'，权值为w。显然，当f(d)最大时，前d'天的收益也最大。因此，f(d) = f(d') + w。 
　　于是，得到状态转移方程： 
[img]http://www.chinaschool.org/aosai/lwjl/images/02-0222-02.gif[/img] 
　　 
其中，x.d'表示线段x的左端点，x.w表示x的权值。 
 
 
 
　　考虑k≠1的情况。 
　　前d天收益第k大的方案中，前j天(j < d)的收益也是前k大的。因此k≠1的情况可以和k=1的情况类似处理。如果要求的最后结果为第k大，只要在每一个阶段都保留前k大的结果。设f(d, n)为前d天可以达到的第n大收益。在计算f(d)的过程中，每次处理x∈[img]http://www.chinaschool.org/aosai/lwjl/images/02-0222-01.gif[/img] 时，可以建立临时数组g，g[i]表示选择了线段x，前d天可以达到的第i大的收益值。于是，g[i] = f(d', i) + x.w (1 ≤ i ≤ k)，然后再把g和f(d)进行归并取前k大。 
 
 
 
[复杂度] 
　　f的每个元素都是长整型的，因此需要367*100*4 = 146800 bytes的空间。线段集合S最多有20000个元素，每个元素要8 bytes，一共要20000*8 = 160000 bytes。因此本一共大约要300K，是可以承受的。这里，f(d)使用指针数组，而[img]http://www.chinaschool.org/aosai/lwjl/images/02-0222-01.gif[/img]则用链表存储。 
 
 
 
　　按天数划分阶段，实际上处理了每条线段，对一条线段的处理是求临时数组g和归并排序这两个过程，这两项的复杂度都是O(k)级的，所以算法总的复杂度O(r k)，可以接受。 
 
 
 
[小结] 
　　实际上该题就是把求最大值推广到了求第k大值，按照求最大值的动态规划，可以得出该题的解法。 
 
 
 
[参考程序] 
 
 
 
{$R-,Q-,S-,T-,V-,W-,X-,Y-} 
const 
　FileIn = 'honey.ina'; 
　FileOut = 'honey.out'; 
　Days : array[0..12]of integer 
　　　= (0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365); 
type 
　TDay = ^PDay; 
　PDay = record 
　　　　d1, d2 : integer; 
　　　　GType : byte; 
　　　　Pay : Longint; 
　　　　next : TDay; 
　　　end; 
　EachDay = array[1..100]of Longint; 
var 
　Request : array[1..366]of TDay; 
　　r : integer; 
　k, k2, t : byte; 
　　latest : integer; 
　　　cost : array[1..100]of longint; 
　ti, ans : Longint; 
　　　　d : array[0..366]of ^EachDay; 
 
 
 
procedure Initialize; 
var day1, day2 : integer; 
　　　i, code : integer; 
　　　　　　F : text; 
　　　　　　s : string; 
　p : TDay; 
 
 
 
　procedure process; 
　var m, d, j : byte; 
　　s1 : string; 
　begin 
　　j := pos(' ', s); s1 := copy(s, 1, j - 1); delete(s, 1, j + 3); 
 
 
 
　　j := pos('/', s1); val(copy(s1, 1, j - 1), m, code); 
　　val(copy(s1, j + 1, length(s1) - j), d, code); 
　　day1 := days[m - 1] + d; 
 
 
 
　　j := pos(' ', s); s1 := copy(s, 1, j - 1); 
　　delete(s, 1, j); 
 
 
 
　　j := pos('/', s1); val(copy(s1, 1, j - 1), m, code); 
　　val(copy(s1, j + 1, length(s1) - j), d, code); 
　　day2 := days[m - 1] + d - 1; 
 
 
 
　　new(p); 
　　p^.d1 := day1; 
　　p^.d2 := day2; 
　　val(s, p^.Gtype, code); 
　　p^.next := request[day2]; 
　　request[day2] := p; 
 
 
 
　　if day2 > latest then latest := day2; 
　end; 
 
 
 
begin 
　assign(f, filein); reset(f); 
　readln(f, k, t); 
　readln(f, i); 
　if (i mod 400 = 0) or (i mod 4 = 0) and (i mod 100 <> 0) then 
　　for i := 2 to 12 do inc(days[i]); 
　readln(f, r); 
 
 
 
　for i := 1 to 366 do request[i] := nil; 
 
 
 
　for i := 1 to r do 
　begin 
　　readln(f, s); 
　　process; 
　end; 
　for i := 1 to t do readln(f, cost[i]); 
　close(f); 
 
 
 
　for i := 1 to latest do 
　begin 
　　p := request[i]; 
　　while p <> nil do 
　　begin 
　　　with p^ do pay := cost[gtype] * (d2 - d1 + 1); 
　　　p := p^.next; 
　　end; 
　end; 
 
 
 
　k2 := k * 2; 
end; 
 
 
 
procedure Dynamic; 
var i, j, l : integer; 
　po, p1, p2, p3 : integer; 
　t : longint; 
　p : TDay; 
　f : text; 
　g : array[1..200]of longint; 
 
 
 
procedure Sort(l, r : integer); 
var 
　i, j : byte; 
　x, y : longint; 
begin 
　i := l; j := r; x := g[(l + r) div 2]; 
　repeat 
　　while g[i] > x do i := i + 1; 
　　while x > g[j] do j := j - 1; 
　　if i <= j then 
　　begin 
　　　y := g[i]; g[i] := g[j]; g[j] := y; 
　　　i := i + 1; j := j - 1; 
　　　end; 
　　until i > j; 
　　if l < j then Sort(l, j); 
　　if i < r then Sort(i, r); 
　end; 
 
 
 
begin 
　for i := 0 to latest do new(d[i]); 
　d[0]^[1] := 0; 
　for i := 2 to k do d[0]^[i] := -1; 
 
 
 
　for j := 1 to latest do 
　begin 
　　p := Request[j]; 
　　d[j]^ := d[j - 1]^; 
　　while p <> nil do 
　　begin 
　　　with p^ do 
　　　begin 
　　　　for i := 1 to k do 
　　　　begin 
　　　　　if d[d1 - 1]^[i] <> -1 then 
　　　　　　g[i] := d[d1 - 1]^[i] + pay 
　　　　　　else 
　　　　　g[i] := -1; 
　　　　g[i + k] := d[j]^[i]; 
　　　end; 
　　　sort(1, k2); 
　　　p1 := 1; 
　　　p3 := 1; 
　　　d[j]^[p3] := -1; 
　　　while p1 < 2 * k do 
　　　begin 
　　　　if g[p1] = g[p1 + 1] then inc(p1) 
　　　　else 
　　　　　begin 
　　　　　　d[j]^[p3] := g[p1]; 
　　　　　　inc(p3); 
　　　　　　if p3 > k then break; 
　　　　　inc(p1); 
　　　　　end; 
　　　　end; 
　　　　while p3 < k do 
　　　　begin 
　　　　　inc(p3); 
　　　　d[j]^[p3] := -1; 
　　　　end; 
　　　end; 
　　　p := p^.next; 
　　end; 
　end; 
　assign(f, fileout); rewrite(f); 
　writeln(f, d[latest]^[k]); 
　close(f); 
end; 
 
 
 
 
begin 
　ti := meml[$40:$6c]; 
 
 
 
　Initialize; 
　Dynamic; 
 
 
 
　writeln((meml[$40:$6c] - ti) / 18.2 : 0 : 2) 
end.

主题：《快乐的蜜月》

回复列表（共3个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：《快乐的蜜月》

回复列表 （共3个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共3个回复）