jiry_2's Blog

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.
			

大水题，按照时间sort一下然后用类似于最长不下降子序列的算法水掉，虽然是m2的算法但是并不慢。

program p1207;
	type
		yanshu=record
			time,x,y:longint;
		end;
	var
		x:array[0..10000] of yanshu;
		f:array[0..10000] of longint;
		i,j,n,m:longint;
	procedure sort(first,en:longint);
		var
			i,j:longint;
		begin
			i:=first; j:=en; x[0]:=x[i];
			while i<j do begin
				while (i<j) and (x[0].time<=x[j].time) do dec(j);
				if i<j then x[i]:=x[j];
				while (i<j) and (x[0].time>x[i].time) do inc(i);
				if i<j then x[j]:=x[i];
			end;
			x[i]:=x[0];
			if i>first+1 then sort(first,i-1);
			if i<en-1 then sort(i+1,en);
		end;
	begin
		readln(n,m);
		for i:=1 to m do
			readln(x[i].time,x[i].x,x[i].y);
		sort(1,m);
		for i:=1 to m do
			f[i]:=1;
		for i:=2 to m do
			for j:=1 to i-1 do
				if (f[j]+1>f[i]) and (abs(x[i].x-x[j].x)+abs(x[i].y-x[j].y)<=x[i].time-x[j].time) then
					f[i]:=f[j]+1;
		j:=0;
		for i:=1 to m do
			if f[i]>j then j:=f[i];
		writeln(j);
	end.

对于每个第二行的点与其有关的只有第一行的三个点，给左边的赋权1，中间的赋权2，右边的赋权4，那么对于每个点都有8个情况，分别对应0--7.而这个是没后效性的，可以用动规解，不多说，看代码。话说动规的代码真的好短。

program p1088;
	var
		x:array[0..20000,0..7] of int64;
		y:array[1..20000] of longint;
		i,j,n:longint;
	begin
		readln(n);
		for i:=1 to n do
			read(y[i]);
		fillchar(x,sizeof(x),0);
		x[0,0]:=1;
		x[0,4]:=1;
		for i:=1 to n-1 do
			if y[i]=0 then
				x[i,0]:=x[i-1,0]+x[i-1,1]
			else if y[i]=1 then begin
				x[i,1]:=x[i-1,2]+x[i-1,3];
				x[i,2]:=x[i-1,4]+x[i-1,5];
				x[i,4]:=x[i-1,0]+x[i-1,1];
			end else if y[i]=2 then begin
				x[i,3]:=x[i-1,6]+x[i-1,7];
				x[i,6]:=x[i-1,4]+x[i-1,5];
				x[i,5]:=x[i-1,2]+x[i-1,3];
			end else if y[i]=3 then 
				x[i,7]:=x[i-1,6]+x[i-1,7];
		if y[n]=0 then writeln(x[n-1,0]+x[n-1,1])
			else if y[n]=1 then writeln(x[n-1,2]+x[n-1,3]+x[n-1,4]+x[n-1,5])
				else if y[n]=2 then writeln(x[n-1,6]+x[n-1,7]);
	end.

以天为状态，则f[i]=min(dj[1,i]*i,dj[j,i]*(i-j+1)+k+f[j-1](2<=j<=i))，dj[i,j]表示第i天到第j天均走同样的路线时的最短路。不需要初始化，在过程中要用到位运算来降低时间复杂度，详细见代码。

program p1003;
	type
		bian=record
			next,point,w:longint;
		end;
	var
		b:array[1..1000000] of bian;
		p,two,d:array[1..30] of longint;
		x,f:array[0..200] of int64;
		len,i,j,n,m,k,e,q,k1,k2,k3,maxn:longint;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].w:=k3;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,k3);
		end;
	function min(k1,k2:int64):int64;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function findmin:longint;
		var
			i,j,k:longint;
		begin
			k:=maxlongint; j:=0;
			for i:=1 to m do
				if (d[i]<k) and (d[i]<>-1) then begin
					k:=d[i];
					j:=i;
				end;
			exit(j);
		end;
	procedure push(k1,k2:longint);
		var
			i,j:longint;
		begin
			i:=p[k1];
			while i<>0 do begin
				j:=b[i].point;
				if (b[i].w+d[k1]<d[j]) and (k2 and two[j]=0) then 
					d[j]:=b[i].w+d[k1];
				i:=b[i].next;
			end;
			d[k1]:=-1;
		end;
	function dj(k:longint):longint;
		var
			i,j,now:longint;
		begin
			fillchar(d,sizeof(d),$3f);
			d[1]:=0;
			for i:=1 to m do begin
				now:=findmin;
				if now=m then exit(d[m]);
				push(now,k);
			end;
		end;
	begin
		readln(n,m,k,e);
		len:=0;
		fillchar(b,sizeof(b),0);
		fillchar(p,sizeof(p),0);
		for i:=1 to e do begin
			readln(k1,k2,k3);
			add(k1,k2,k3);
		end;
		two[1]:=1;
		for i:=2 to m do
			two[i]:=two[i-1]*2;
		readln(q);
		fillchar(x,sizeof(x),0);
		for i:=1 to q do begin
			readln(k1,k2,k3);
			for j:=k2 to k3 do
				x[j]:=x[j] or two[k1];
		end;
		fillchar(f,sizeof(f),$3f);
		maxn:=f[1];
		f[0]:=0;
		for i:=1 to n do begin
			k1:=x[i];
			for j:=i downto 2 do begin
				k2:=dj(k1);
				if k2<>maxn then begin
					f[i]:=min(f[i],k2*(i-j+1)+k+f[j-1]);
					k1:=k1 or x[j-1];
				end else break;
			end;
			k2:=dj(k1);
			if k2<>maxn then f[i]:=min(f[i],k2*i);
		end;
		writeln(f[n]);
	end.

背包，不用多说了。

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.