9
21
2013
0

【BZOJ2431】【HAOI2009】逆序对数列【DP】

O(NK^2)的算法是果果的,O(NK)的算法只要用一个TOT来计算前缀和就可以了,边界+-1搞了一会儿就A了。

program p2431;
	var
		x:array[0..1,0..1000] of longint;
		n,k,i,j,tot,k1,k2:longint;
	begin
		readln(n,k);
		fillchar(x,sizeof(x),0);
		x[0,0]:=1;
		for i:=1 to n do begin
			k1:=i mod 2; k2:=1-k1;
			x[k1,0]:=x[k2,0]; tot:=x[k2,0];
			for j:=1 to k do begin
				if j<i then tot:=(tot+x[k2,j]) mod 10000 else tot:=(tot-x[k2,j-i]+x[k2,j]+10000) mod 10000;
				x[k1,j]:=tot;
			end;
		end;
		writeln(x[k1,k]);
	end.
			
Category: DP | Tags: | Read Count: 1985

登录 *


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