Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 646 Solved: 393
神犇航空开展了一项载客特技飞行业务。每次飞行长N个单位时间,每个单位时间可以进行一项特技动作,可选的动作有K种,每种动作有一个刺激程度Ci。如果连续进行相同的动作,乘客会感到厌倦,所以定义某次动作的价值为(距上次该动作的时间)*Ci,若为第一次进行该动作,价值为0。安排一种方案,使得总价值最大。
第一行,两个数,N和K,如上所述; 第二行,K个正整数,表示K种动作的Ci值。
仅一行,一个整数,表示最大总价值。
5 2 2 2
12
数据规模及约定 对于10%的测试数据,N<=20,K<=3 对于全部的测试数据,1<=N<=1000,1<=K<=300,0<=Ci<=1000。
题解:这个嘛,是个萌萌哒贪心啦啦啦——先从大到小排序,然后依次往两边摆上 ,不难证明其最优性
1 var
2 i,j,k,m,n,ll,l,r,x,y:longint;
3 a:array[0..2000] of longint;
4 procedure swap(var x,y:longint);inline;
5 var z:longint;
6 begin
7 z:=x;x:=y;y:=z;
8 end;
9 procedure sort(l,r:longint);
10 var i,j,x,y:longint;
11 begin
12 i:=l;j:=r;x:=a[(l+r) div 2];
13 repeat
14 while a[i]>x do inc(i);
15 while a[j]<x do dec(j);
16 if i<=j then
17 begin
18 swap(a[i],a[j]);
19 inc(i);dec(j);
20 end;
21 until i>j;
22 if i<r then sort(i,r);
23 if l<j then sort(l,j);
24 end;
25 begin
26 readln(n,m);
27 for i:=1 to m do read(a[i]);
28 readln;
29 sort(1,m);
30 x:=1;y:=n;
31 for i:=1 to m do
32 begin
33 ll:=ll+(y-x)*a[i];
34 inc(x);dec(y);
35 if x>=y then break;
36 end;
37 writeln(ll);
38 readln;
39 end.