noip普及组复赛模拟试题15（附答案）(2)

1.当a[i]<>b[j]时，f[i,j]=f[i-1,j]（因为a[i]<>b[j]，所以说就等价于在1~i-1找一个等于a[k]=b[j]，如果a[i-1]=b[j]，那么就是从f[i-1,j]转移而来；如果a[i-1]<>b[j]，那么就是在1~i-2中去找一个，对于那些不相等的，是没有贡献的，可以直接从上一个相等的转移而来，这样就少了第1维的枚举，从O(N^4)一下降为了O(N^3))。 2.当a[i]=b[j]时，f[i,j]=max(f[i-1,k])+1。

这样我们着眼于从状态转移上下功夫，降了一维。这道题很显然是很难减少状态数的，状态数就定下来是O(N^2)了，要想继续优化，必须从状态的转移上想办法。。 再说更优的O(N^2)的算法：

在a[i]<>b[j]时，我们已经将状态转移的复杂度降为了O(1),已经无法再优化了。。 于是我们就只有优化a[i]=b[j]时的转移，如何优化？

我们要一个max(f[i-1,k])(b[j]=a[i]>b[k])。所以我们要求这个max，那么就要看能否不用O(N)的扫描，而是看能否用O(1)的代价找到这个max，或者是用O(logN)的复杂度转移都是能够承受的了。。那么怎么求max?

我们发现要求的是i-1层，这一层是全部求出来了的，对于我们这次对第i层求解，每次都要扫描重复的，这就有冗余关系，为了减少冗余，我们可以把max(f[i-1,k])保存下来，因为j是递增的，所以每次的k也就增加一个，我们只需判断这个新增加的k与max的大小。。也就是说，在求解f[i,j]的过程中，我们就可以把f[i-1,k]中最大的存下来，为每次a[i]=b[j]的转移作准备。。

于是，这道题就从状态转移上由O(N^2)变为了O(1)，这个是很优的了。应该已经达到了时间复杂度的下界了。

[贪心dp]过河游戏

[问题描述] 有一个大晴天，Oliver与同学们一共N人出游，他们走到一条河的东岸边，想要过河到西岸。而东岸边有一条小船。船太小了，一次只能乘坐两人。每个人都有一个渡河时间T，船划到对岸的时间等于船上渡河时间较长的人所用时间。现在已知N个人的渡河时间T，Oliver想要你告诉他，他们最少要花费多少时间，才能使所有人都过河。 注意，只有船在东岸（西岸）的人才能坐上船划到对岸。 [输入格式]

输入文件第一行为人数N，以下有N行，每行一个数。 第i+1行的数为第i个人的渡河时间。 [输出格式]

输出文件仅包含一个数，表示所有人都渡过河的最少渡河时间。 [样例输入] 4 6 7 10 15

[样例输出]

42

[样例解释]

初始：东岸{1，2，3，4}，西岸{}

第一次：东岸{3，4}，西岸{1，2} 时间7 第二次：东岸{1，3，4}，西岸{2} 时间6 第三次：东岸{1}，西岸{2，3，4}，时间15 第四次：东岸{1，2}，西岸{3，4} 时间7 第五次：东岸{}，西岸{1，2，3，4} 时间7

所以总时间为7+6+15+7+7=42，没有比这个更优的方案。 [数据范围]

对于40%的数据满足N≤8。

对于100%的数据满足N≤100000。

【解题思路】这个题我想了很久，我一直以为是个贪心题，却没有注意到状态的选择并不是单一的。。。。。。。。。。结果自己推了好久，在那模拟n=3..8的情况，还推了个公式，结果错了，因为我把值等于下标推得，但是实际情况显然不是那样的，也正因为值的不同，所以不能用单纯的贪心来做。。我们不难发现对于每一个人，我们都是有两种选择。

如果是还剩最后两个人，那么就可以是先把1,2运过去，然后1回来，再把那两个送过去，然后2回来接1,最后1,2再过去。

如果是还剩最后一个人，那么就是用1回来接他，然后一起过去。 所以说：f[n]=min(f[i-1]+a[i]+a[1],f[i-2]+a[1]+2*a[2]);

program river; uses math;

var a,f:array[1..100000] of longint; n:longint; procedure init; begin

assign(input,'river.in'); reset(input);

assign(output,'river.out'); rewrite(output); end;

procedure terminate; begin

close(input); close(output); halt; end;

procedure qsort(s,t:longint); var i,j,m,x:longint; begin

m:=(s+t) shr 1;

x:=a[m]; a[m]:=a[s]; a[s]:=x; i:=s; j:=t; x:=a[i]; repeat

while (i if ia[i]) do inc(i);

if i

until i=j; a[i]:=x;

inc(i); dec(j);

if i

procedure main; var i,j,x:longint; begin

readln(n);

for i:=1 to n do readln(a[i]); qsort(1,n); f[1]:=a[1]; f[2]:=a[2];

for i:=3 to n do begin

f[i]:=min(f[i-2]+a[i]+a[1]+2*a[2],f[i-1]+a[i]+a[1]); end;

writeln(f[n]); end; begin init; main;

terminate; end. 输入 8 5 7 9 10 18 25 34 42

输出 141 输入 25 7 10 14 18 20 25 40 100 110

135 146 189 191 201 205 212 233 246 275 289 300 310 320 333

345 输出 2513