7
31
2013
0

【BZOJ2748】【HAOI2012】音量调节【DP】

背包,不用多说了。



program p2748;
	var
		f:array[0..50,0..1000] of boolean;
		x:array[1..100] of longint;
		ans,n,maxn,i,j,k:longint;
	begin
		readln(n,ans,maxn);
		for i:=1 to n do 
			read(x[i]);
		fillchar(f,sizeof(f),false);
		f[0,ans]:=true;
		for i:=1 to n do
			for j:=0 to maxn do begin
				if (j+x[i]<=maxn) and (f[i-1,j]=true) then
					f[i,j+x[i]]:=true;
				if (j-x[i]>=0) and (f[i-1,j]=true) then 
					f[i,j-x[i]]:=true;
			end;
		j:=-1;
		for i:=maxn downto 0 do
			if f[n,i]=true then begin
				j:=i;
				break;
			end;
		writeln(j);
	end.
Category: DP | Tags: | Read Count: 922

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

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