[NOIP集训]10月18日

时间：2021-11-17 13:51:34

今天的文件夹：10月18日.zip

今天脑子转不起来，想不出来动规了。

Orz @张翰文学神

T1:快排，然后求连续数字的长度，简单判断即可。

T2：

 

题2、 养zsc(pig.pas/c/cpp)

【题目描述】

    你有一个zsc圈，有$N$头zsc，每天你最多可以杀一头zsc卖钱，获益就是zsc的体重。但是每过一天每头zsc的体重都会下降$P_i$（当然，如果zsc体重$ \leq 0$了，自然获利就是$0$），问$K$天内你的最大获利。

【输人文件】

    第一行两个数$N,K$；

    第二行$N$个数表示zsc的初始重量$A_i$；

    第三行$N$个数表示$P_i$。

【输出文件】

    一行一个数表示最大获利。

【样例输入】

    2 2

    10 10

    1 2

【样例输出】

19

 

【数据规模】

    对于20％的数据，满足$1 \leq N \leq 20$；

    对于100％的数据，满足$1 \leq N \leq 1000$，初始重量$ \leq 10^5$。

 

这道题属于DP中的一类，它的状态转移顺序并不是题目给出的，而是要自己构造。

我们先证明一个定理：如果$P_i > P_j$，那么在其他顺序不变的情况下，先杀掉第$i$只zsc的解，不会比先杀第$j$只zsc的解差。

证明：不妨设杀掉zsc的顺序为数组$ord$，其中$ord_k$表示杀掉的第$k$只zsc的原序号。设$ord_x=i$，$ord_y=j$，若$x>y$，那么此时杀掉这两只zsc的总收益为

\[\max (0,A_i-(x-1)*P_i)+\max (0,A_j-(y-1)*P_j)\]

而交换了顺序后（即$ord_x=j$，$ord_y=i$），总收益为

\[\max (0,A_j-(x-1)*P_j)+\max (0,A_i-(y-1)*P_i)\]

这里有多种情况，这里举例分析出现的数据都大于0的情况，若出现等于0或小于0，根据条件也可同样证明。

假设都大于0，那么上述两式可以化简为

\[A_i+A_j-(x-1)*P_i-(y-1)*P_j\]

和

\[A_i+A_j-(x-1)*P_j-(y-1)*P_i\]

又因为$x-1>y-1$，$P_i>P_j$，由排序不等式

\[(x-1)*P_i+(y-1)*P_j>(x-1)*P_j+(y-1)*P_i\]

进而有

\[A_i+A_j-(x-1)*P_i-(y-1)*P_j<A_i+A_j-(x-1)*P_j-(y-1)*P_i\]

于是得证。

这样看来，在最后的最优解中，$P$数组必然是递减的。因此我们先对所有zsc按$P$值排序，这之后选出zsc来杀的顺序就是一定的，只要选出$K$只，求最优解。这就转化为了01背包模型。

T3:

 

3、zsc处理（rubbish.pas/c/cpp）

【问题描述】

    聚会结束，留下许多zsc。Candy家里总共有$n$个zsc等待处理，每个zsc对于candy和飘飘乎居士处理的时间都是不同的，而且每个zsc只需要一个人处理。当然，candy和飘飘乎居士可以同时处理不同的zsc。记两人中耗费最长时间为最后总时间。candy希望能够尽快的处理完所有的zsc，因此，他想要知道处理完这些zsc最少需要耗费多少时间？

【输入格式】

    第一行一个正整数$n$，表示一共有$n$个zsc需要处理

    接下来一个$2*n$的矩阵。

    矩阵第一行第$i$个数表示candy处理第$i$个zsc所需消耗的时间

    矩阵第二行第$i$个数表示飘飘乎居士处理第$i$个zsc所需消耗的时间

【输出格式】

    一行，最后耗费的时间

【输入样例】

    5

    2 4 1 4 5

    2 1 3 4 1

【输出样例】

    5

【样例说明】

    candy完成zsc 3与zsc 4的清理，耗时为5

    飘飘乎居士完成zsc 1 2 5的清理，耗时为4，由于candy耗费的时间较长，所以记candy耗费时间为最后总时间，所以最后答案为5。

【数据规模】

    对于30%的数据 $0<n \leq 30$

    对于100%的数据 $0<n \leq 1000$,Candy和飘飘乎居士处理每个zsc的时间$ \leq 10$，对任何一个人处理所有zsc时间总和$ \leq 4000$

 一道DP杂题，思路到了就很水了。有的人看到"最大值最小"就去想什么二分答案、并查集等，其实这题是个DP。

考虑数据范围，我们分别用$a_i,b_i$分别表示两人处理第$i$件zsc的用时，$ans[i][j]$表示处理前$i$个zsc，其中candy用时为$j$时，飘飘乎居士用的最短时间。状态转移方程为

\[ans[i][j]=\min(ans[i-1][j]+b_i,ans[i-1][j-a_i])\]

其中的两种决策分别是让飘飘乎居士和candy来处理这一件zsc。当然，对于$j$小于$a_i$的情况，不考虑后一种情况即可。

最后输出的是在所有$i$中，$i+ans[n][i]$的最小值。

T4:容我再想两天。。。

代码：

[NOIP集训]10月18日[NOIP集训]10月18日
 1 program amblygonite;
 2 var
 3     a:array[1..1100000] of longint;
 4     n,i,j,k,m:longint;
 5 procedure qsort(l,r:longint);
 6 var
 7     i,j,x,y:longint;
 8 begin
 9     i:=l;
10     j:=r;
11     x:=a[(l+r) div 2];
12     repeat
13         while a[i]<x do
14             inc(i);
15         while x<a[j] do
16             dec(j);
17         if not(i>j) then
18         begin
19             y:=a[i];
20             a[i]:=a[j];
21             a[j]:=y;
22             inc(i);
23             dec(j);
24         end;
25     until i>j;
26     if l<j then
27         qsort(l,j);
28     if i<r then
29         qsort(i,r);
30 end;
31 begin
32     assign(input,'amblygonite.in');
33     reset(input);
34     assign(output,'amblygonite.out');
35     rewrite(output);
36     readln(n);
37     if n=0 then 
38     begin 
39         writeln(0); 
40         close(input);
41         close(output);
42         halt; 
43     end;
44     for i:=1 to n do 
45         read(a[i]);
46     readln;
47     qsort(1,n);
48     j:=0;
49     m:=0;
50     while j<n do
51     begin
52         inc(j);
53         k:=j;
54         while (a[j+1]=a[j])and(j<n) do 
55             inc(j);
56         inc(m,(j-k+1) div 10);
57     end;
58     writeln(m);
59     close(input);
60     close(output);
61 end.
amblygonite.pas
[NOIP集训]10月18日[NOIP集训]10月18日
 1 program pig;
 2 uses math;
 3 var
 4     a,p:array[1..1000] of longint;
 5     n,k:longint;
 6     ans:array[0..1000] of longint;
 7     i,j,ls:longint;
 8 begin
 9     assign(input,'pig.in');
10     reset(input);
11     assign(output,'pig.out');
12     rewrite(output);
13     readln(n,k);
14     for i:=1 to n do
15         read(a[i]);
16     for i:=1 to n do
17         read(p[i]);
18     for i:=1 to n-1 do
19         for j:=i+1 to n do
20             if (p[i]<p[j])or((p[i]=p[j])and(a[i]<a[j])) then
21             begin
22                 ls:=a[i]; a[i]:=a[j]; a[j]:=ls;
23                 ls:=p[i]; p[i]:=p[j]; p[j]:=ls;
24             end;
25     fillchar(ans,sizeof(ans),0);
26     for i:=1 to n do
27         for j:=k downto 1 do
28             ans[j]:=max(ans[j],ans[j-1]+max(0,a[i]-(j-1)*p[i]));
29     writeln(ans[k]);
30     close(input);
31     close(output);
32 end.
pig.pas
[NOIP集训]10月18日[NOIP集训]10月18日
 1 program rubbish;
 2 uses math;
 3 var
 4     n:longint;
 5     a,b:array[1..1000] of longint;
 6     i,j,k:longint;
 7     ok:array[0..1000,0..4000] of longint;
 8     sum1,ans:longint;
 9 begin
10     assign(input,'rubbish.in');
11     reset(input);
12     assign(output,'rubbish.out');
13     rewrite(output);
14     readln(n);
15     sum1:=0;
16     for i:=1 to n do
17     begin
18         read(a[i]);
19         sum1:=sum1+a[i];
20     end;
21     for i:=1 to n do
22         read(b[i]);
23     fillchar(ok,sizeof(ok),$3f);
24     ok[0,0]:=0;
25     for i:=1 to n do
26         ok[i,0]:=ok[i-1,0]+b[i];
27     for i:=1 to n do
28     begin
29         for j:=0 to a[i]-1 do
30             ok[i,j]:=ok[i-1,j]+b[i];
31         for j:=a[i] to sum1 do
32             ok[i,j]:=min(ok[i-1,j]+b[i],ok[i-1,j-a[i]]);
33     end;
34     ans:=$3f3f3f3f;
35     for i:=1 to sum1 do
36         ans:=min(ans,max(i,ok[n,i]));
37     writeln(ans);
38     close(input);
39     close(output);
40 end.
rubbish.pas
标签：

相关文章