10
21
2013
2

【BZOJ2697】特技飞行【贪心】

开始以为是DP,但是仔细一想,动作k创造的价格只取决于它第一次出现的时间Sk和最后一次出现的时间Ek,则它创造的价值只可能为(Ek+Sk)*Ck。所以我们每次找最大价值的动作放在两侧直到放不下为止。

program p2697;
	var
		x:array[1..500] of longint;
		i,j,k,n,k1,max,where,tot:longint;
	begin
		readln(n,k);
		for i:=1 to k do
			read(x[i]);
		k1:=n+1; tot:=0;
		for i:=1 to k do begin
			k1:=k1-2;
			if k1<=0 then break;
			max:=-1;
			for j:=1 to k do
				if max<x[j] then begin
					max:=x[j]; where:=j;
				end;
			x[where]:=-1; tot:=tot+k1*max;
		end;
		writeln(tot);
	end.
Category: 贪心 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com