[NOIP集训]10月18日

今天的文件夹：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:容我再想两天。。。

代码：

program amblygonite; var a:array[1..1100000] of longint; n,i,j,k,m:longint; procedure qsort(l,r:longint); var i,j,x,y:longint; begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a[i]<x do inc(i); while x<a[j] do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; begin assign(input,'amblygonite.in'); reset(input); assign(output,'amblygonite.out'); rewrite(output); readln(n); if n=0 then begin writeln(0); close(input); close(output); halt; end; for i:=1 to n do read(a[i]); readln; qsort(1,n); j:=0; m:=0; while j<n do begin inc(j); k:=j; while (a[j+1]=a[j])and(j<n) do inc(j); inc(m,(j-k+1) div 10); end; writeln(m); close(input); close(output); end.

program pig; uses math; var a,p:array[1..1000] of longint; n,k:longint; ans:array[0..1000] of longint; i,j,ls:longint; begin assign(input,'pig.in'); reset(input); assign(output,'pig.out'); rewrite(output); readln(n,k); for i:=1 to n do read(a[i]); for i:=1 to n do read(p[i]); for i:=1 to n-1 do for j:=i+1 to n do if (p[i]<p[j])or((p[i]=p[j])and(a[i]<a[j])) then begin ls:=a[i]; a[i]:=a[j]; a[j]:=ls; ls:=p[i]; p[i]:=p[j]; p[j]:=ls; end; fillchar(ans,sizeof(ans),0); for i:=1 to n do for j:=k downto 1 do ans[j]:=max(ans[j],ans[j-1]+max(0,a[i]-(j-1)*p[i])); writeln(ans[k]); close(input); close(output); end.

program rubbish; uses math; var n:longint; a,b:array[1..1000] of longint; i,j,k:longint; ok:array[0..1000,0..4000] of longint; sum1,ans:longint; begin assign(input,'rubbish.in'); reset(input); assign(output,'rubbish.out'); rewrite(output); readln(n); sum1:=0; for i:=1 to n do begin read(a[i]); sum1:=sum1+a[i]; end; for i:=1 to n do read(b[i]); fillchar(ok,sizeof(ok),$3f); ok[0,0]:=0; for i:=1 to n do ok[i,0]:=ok[i-1,0]+b[i]; for i:=1 to n do begin for j:=0 to a[i]-1 do ok[i,j]:=ok[i-1,j]+b[i]; for j:=a[i] to sum1 do ok[i,j]:=min(ok[i-1,j]+b[i],ok[i-1,j-a[i]]); end; ans:=$3f3f3f3f; for i:=1 to sum1 do ans:=min(ans,max(i,ok[n,i])); writeln(ans); close(input); close(output); end.