# 20 条题解

• @ 2020-11-24 07:41:17
``````program ctsc2000;
var d1,l1,d2,k,y,z,y1,b,c,d,e,r,t,n,m,i,j,l:longint;
a:array[1..366,1..20000]of record
x,y,z,q:longint;
end;
s1,s:string;
t1:char;
p:array[1..130]of longint;
q,temp:array[0..100]of longint;
f:array[0..366,0..732]of longint;
num:array[1..366]of integer;
function calc(b,c:integer):longint;
var s,i:integer;
begin
s:=0;
for i:=1to b-1 do
s:=s+q[i];
s:=s+c;
calc:=s;
end;
procedure sort(w,i,j:integer);
var x,y,mid,s:longint;
begin
x:=i;
y:=j;
mid:=f[w,(i+j)div 2];
repeat
while f[w,x]>mid do inc(x);
while f[w,y]<mid do dec(y);
if x<=y then
begin
s:=f[w,x];
f[w,x]:=f[w,y];
f[w,y]:=s;
dec(y);inc(x);
end;
until x>y;
if i<y then sort(w,i,y);
if j>x then sort(w,x,j);
end;
begin
fillchar(num,sizeof(num),0);
q[0]:=0;
for i:=1to 12 do
case i of
1,3,5,7,8,10,12:q[i]:=31;
4,6,9,11:q[i]:=30;
end;
if (y mod 400=0)or ((y mod 4=0)and(y mod 100<>0))then
begin
y1:=366;
q[2]:=29;
end
else begin q[2]:=28;y1:=365;end;
for i:=1to r do
begin
j:=pos(' ',s);s1:=copy(s,1,j-1);
delete(s,1,j+3);
j:=pos('/',s1);
val(copy(s1,1,j-1),b);
val(copy(s1,j+1,length(s1)-j),c);
j:=pos(' ',s);
s1:=copy(s,1,j-1);
delete(s,1,j);
j:=pos('/',s1);
val(copy(s1,1,j-1),d);
val(copy(s1,j+1,length(s1)-j),e);
d1:=calc(b,c);
d2:=calc(d,e);
inc(num[d2]);
a[d2,num[d2]].x:=d1;
a[d2,num[d2]].y:=d2-d1;
val(s,a[d2,num[d2]].z);
end;
for i:=1to t do
fillchar(f,sizeof(f),0);
for i:=1to y1  do
begin
for j:=1to k do  f[i,j]:=f[i-1,j];
for j:=1 to num[i] do
begin
fillchar(temp,sizeof(temp),0);
for l:=k+1 to 2*k do
f[i,l]:=f[a[i,j].x,l-k]+a[i,j].y*p[a[i,j].z];
sort(i,1,2*k);
m:=1;
for l:=1to k do
begin
if f[i,m]=0 then break
else
begin
while f[i,m]=f[i,m+1] do inc(m);
temp[l]:=f[i,m];
inc(m);
if m>2*k then begin
for z:=l+1to k do temp[z]:=0;break;end;
end;
end;
for l:=1to k do
f[i,l]:=temp[l];
end;
end;
if (k>1)and(f[y1,k]=0)and(f[y1,k-1]=0) then writeln('-1')
else
writeln(f[y1,k]);
end.
``````
• @ 2009-10-30 14:57:11

艰难地过掉了……

这题还真是大杂烩啊……

1.输入要处理字符串

2.

（那个y是干嘛的呢？）

哈哈，判断计算天数用的，因为有闰年和平年的区别。

3.DP（K优解）+归并（双队列）

k=1时，我们以天数为阶段,f[i]=max(f,f[day.start]+fee[day.id]*(i-day.start));

day[i]存的是所有以i结束的预约，fee[i]对应id的费用。

那么k>1时呢，类似背包第K优解，建议先做P1412《多人背包》。

f初始都是0

for i:=1 to 总天数 do

{

f[i]:=f; //拒绝该预约

for j:=1 to 结束时间为i的预约个数 do

{

q1取f[i]

q2取加入day的情况(即f[day.start]+fee[day.id]*(i-day.start))

合并q1,q2，去除重复的，前K大存入f[i]，一定要保证f[i]没有重复值。

}

}

输出f[总天数,k] 如果(k>1) and (f[总天数,k-1]=0) 输出-1，因为结果是递增非重复的，前面一个等于0，说明要求的答案是不可达到的。

• @ 2009-08-04 19:56:10

数据规模有问题是真的。我看了一下，人数要有20000。

这个题目直接裸的DP好了，不用归并什么的优化，快排是硬道理。裸的就能AC。

• @ 2009-03-10 23:23:52

序列归并+dp

• @ 2009-02-23 21:02:53

归并排序写错

没有想法那。。。

• @ 2008-11-01 21:17:27

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 228ms

├ 测试数据 10：答案正确... 259ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：559ms

第一题难度5的 第40个AC

当k=1时 f[i]:=max{f,f[day.start]+day.money}

f[i]为第i天 day为结束时间为第i天的第j个预定

day.start为开始时间 day.money为收入

当k>1时 将f[i]变为f即可 意为第i天第k优解 由前面的状态扩展

排序后记录前k个即可。

注意:0也算一种解 不然值得70(本人吃过这样的亏)

• @ 2007-11-07 21:10:26

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

特殊的背包问题。。。保存前K大的状态。程序100行

• @ 2009-10-08 10:14:37

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：25ms

难度五 是唬人的

一次AC 感觉不错！

• @ 2009-10-04 14:24:50

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 56ms

├ 测试数据 07：答案正确... 41ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 181ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：444ms

Dragon 还真是不吉利啊。。。444ms 我汗

• @ 2009-09-13 13:00:19

一个字母打错，冤枉了一早上，注意排序是否正确！！！

• @ 2009-09-12 10:55:02

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

DP+归并

• @ 2009-08-25 15:30:31

AC掉的第一道难度5的,同时也是第一道CTSC的题

• @ 2009-06-16 13:07:00

太囧了

排序写错了

害得我叫了n多次

• @ 2009-06-01 10:32:48

DP + 归并排序（注意解相同只能算一次）

p.s. 这种题难度也有5？虽然是CTSC的……

• @ 2009-04-30 18:34:38

可以看看DD的背包九讲中是如何求K优解的

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

• @ 2008-11-10 22:11:16

水题

• @ 2008-10-27 18:04:44

人算不如天算，唉~~~~

编的长，连检查都都麻烦，

总过不了，晕啊！！！！！！！！！！！！！！！

• @ 2008-08-11 14:00:23

地板...

• @ 2007-07-07 21:39:36

难度5的，就是牛！！！

楼下大牛都写了200行以上吧，看样子我就不用做这题了。

• @ 2009-10-08 16:57:47

sb题，最后1个点找了n久

• 1

ID
1170

8

609

92

15%

4