作业fence解题报告

1、FenceTime Limit:1000MSMemory Limit:30000KTotal Submit:177 Accepted:44DescriptionA team of k (1 = K = 100) workers should paa fence which contains N (1 = N= 16 000) pls numbered from 1 to N from left to right. Each worker i (1 = i =K) should sit in front of the plSi and he may paonly a compacterval (

2、this erval shoulds and for eachmeanst the pls from theerval should be consecutive). Thiscontahe Si pl. Also a worker should not pamoren Li plpaed plhe should receiv$ (1 = Pi = 10 000). A plshould be paedby no morenorker. All the numbers Si should be distinct.Being the teams leader you want to determ

3、ine for each worker theervalt he eshould pa, knowingt the totale should beal. The totalrepresents the sum of the workersale.Write a programt determines the totalale obtained by the K workers.InputThe inpontains:InputN KL1 P1 S1 L2 P2 S2.LK PK SKSemnificationN -the number of the pls; K ? the number o

4、f the workersLi -theal number of plst can be paed by worker iPi -the sum received by worker i for a paed plSi -the plin front of which sits the worker iOutputThe outpontains a singleeger, the totalale.SleInput83331422312357Sle Output17HExplanation of the sle:the worker 1 pas theerval 1, 2;the worker

5、 2 pas theerval 3, 4;the worker 3 pas theerval 5, 7;the worker 4 does not paany plSourceRomania OI 2002问题简介（PKU1821）：K 个工人受雇粉刷一段长度为N 的。工人 I 粉刷的木板长度过 Li（可以为 0），他粉刷的木板必须是连续的，而且必须包含第 Si 号木板。第 I 个工人粉刷一块木板可以得到 Pi 的。现在要你计算机出 K 个工人最多可以得到多少。分析：这个题目明显可以用动态规划解决。求解之前，将 K 个工人按其 Si 值从小到大排序。设 FI，J表示前 I 个工人粉刷前 J 块

6、木板可以得到的最大FI，J=Max FI，J - 1，FI1， J，FI- 1，K 1 + （J-K+1）*Pi。则说明：K 是决策量，必须要满足从第K 到第J 块木板可以被第I 个工人一个人刷。这个算法的时间复杂度为O（K*N2）,太慢了。感觉上这个题目和 NOI2006 第一试第三题有些类似，因此量K 满足单调性。猜想最优决策设求 FI，J时，决策取 K1、K2（假定这两个决策存在，并且 K1=L2,且 S1 比 S2 优的充要条件是：（FI-1，K2-1 FI-1，K1-1）/ Pi (L1 L2)从上面的式子可以看到，L1、L2 是同时递增的，而且 L1 会比 L2 先到达 Li（到达

7、 Li 后就不能再递增了），所以如果在求 FI，J时，决策 K1 不比K2 优，那么，在求所有 FI，K时（KJ）,决策 K1 也肯定不会比 K2 优了。相反，如果求 FI，J时，决策 K1 比 K2 优呢？在求后面的 FI，K时，K1不一定比 K2 优。但是注意到 L1 比 L2 先递增到 Li，不难证明，假设求某个 FI， K时，决策 K1 不比K2 优了，对于今后的求解，K1 也决不比 K2 优。通过上面两步，就能证明决策单调。接下来就能运用一个队列来优化算法了：（1）开一个队列K，队列中元素表示他们在今后有可能成为最优决策量，并且 K1K2= Rthen exit;i :=L; j :

8、=R; x :=nodetrunc(random * (R - L + 1) + L;repeatwhile nodei.s x.s do dec(j);if i j;sort(L, j); sort(i, R);end;sort:=nodej; nodej :=temp;procedure var i, j,queue beginsort(1,solve;k, st,ed, s: long;: array1 . maxm of long;n);for i :=1 to ndo beginst :=1; ed :=0;for j :=1fi, j if fi,to m do begin:=fi - 1, j;j - 1 fi, jthen fi, j :=fi, j - 1;if (st = nodei.S) and (j fi, j then fi, j :=s;end;then从队首取最优决策if (st = nodei.L) then inc(st); 删除队首元素 if (j = nodei.s) then beginwhile (st = (j - queueed) * nodei.P) dodec(ed);inc(ed); queueed :=j; end;thenend;for j end;for iend;solve新决策