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
  readln(k,t);
 readln(y);
 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;
   readln(r);
 for i:=1to r do
  begin
  readln(s);
  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
   read(p[i]);
   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.

艰难地过掉了……

这题还真是大杂烩啊……

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，说明要求的答案是不可达到的。

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

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

序列归并+dp

归并排序写错

没有想法那。。。

编译通过...

├ 测试数据 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(本人吃过这样的亏)

编译通过...

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

难度五 是唬人的

一次AC 感觉不错！

编译通过...

├ 测试数据 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 我汗

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

DP+归并

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

太囧了

排序写错了

害得我叫了n多次

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

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

可以看看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

水题

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

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

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

地板...

难度5的，就是牛！！！

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

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