讨论 - 大牛们看一下

xxwzy 2009-03-06 06:29:00

点我顶贴收藏删除

var i1,i2,i3,i,j,k,n,m,max:longint；

a:array[0..101,0..101]of longint；

f:array[0..101,0..101,0..53]of longint；

shu:array[0..101]of longint；

x:char；

procedure ohzw(i,j:longint)；

var k,jj,kk:longint；

begin

i1:=0；

i2:=0；

i3:=0；

for k:=1 to 52 do

if k<>a[i,j] then

begin

if (f[i-1,j,k]=1) then inc(i1)；

if (f[i-1,j-1,k]=1) then inc(i2)；

if (f[i-1,j+1,k]=1) then inc(i3)；

end；

if (i1>i2)and(i1>i3) then

begin

for k:=1 to 52 do if f[i-1,j,k] = 1 then f[i,j,k]:=1；

if i<=n then

begin if j<m then ohzw(i,j+1) else ohzw(i+1,1)；end；

exit；

end；

if (i3>i2)and(i3>i1) then

begin

for k:=1 to 52 do if f[i-1,j+1,k]=1 then f[i,j,k]:=1；

if i<=n then

begin if j<m then ohzw(i,j+1) else ohzw(i+1,1)；end；

exit；

end；

if (i2>i1)and(i2>i3) then

begin

for k:=1 to 52 do if f[i-1,j-1,k]=1 then f[i,j,k]:=1；

if i<=n then

begin if j<m then ohzw(i,j+1) else ohzw(i+1,1)；end；

exit；

end；

if i1=i2 then

begin

for k:=1 to 52 do if f[i-1,j-1,k]=1 then f[i,j,k]:=1；

if i<=n then

begin if j<m then ohzw(i,j+1) else ohzw(i+1,1)；end；

for jj:=1 to m do

for kk:=1 to 52 do

if f[n,j,k]=1 then inc(shu[j])；

for j:=1 to m do if shu[j]>max then max:=shu[j]；

for j:=1 to m do shu[j]:=0；

for k:=1 to 52 do if f[i-1,j,k]=1 then f[i,j,k]:=1；

if i<=n then

begin if j<m then ohzw(i,j+1) else ohzw(i+1,1)；end；

for jj:=1 to m do

for kk:=1 to 52 do

if f[n,j,k]=1 then inc(shu[j])；

for j:=1 to m do if shu[j]>max then max:=shu[j]；

for j:=1 to m do shu[j]:=0；

end；

if i3=i2 then

begin

for k:=1 to 52 do if f[i-1,j-1,k]=1 then f[i,j,k]:=1；

if i<=n then

begin if j<m then ohzw(i,j+1) else ohzw(i+1,1)；end；

for jj:=1 to m do

for kk:=1 to 52 do

if f[n,j,k]=1 then inc(shu[j])；

for j:=1 to m do if shu[j]>max then max:=shu[j]；

for j:=1 to m do shu[j]:=0；

for k:=1 to 52 do if f[i-1,j+1,k]=1 then f[i,j,k]:=1；

if i<=n then

begin if j<m then ohzw(i,j+1) else ohzw(i+1,1)；end；

for jj:=1 to m do

for kk:=1 to 52 do

if f[n,j,k]=1 then inc(shu[j])；

for j:=1 to m do if shu[j]>max then max:=shu[j]；

for j:=1 to m do shu[j]:=0；

end；

if i1=i3 then

begin

for k:=1 to 52 do if f[i-1,j+1,k]=1 then f[i,j,k]:=1；

if i<=n then

begin if j<m then ohzw(i,j+1) else ohzw(i+1,1)；end；

for jj:=1 to m do

for kk:=1 to 52 do

if f[n,j,k]=1 then inc(shu[j])；

for j:=1 to m do if shu[j]>max then max:=shu[j]；

for j:=1 to m do shu[j]:=0；

for k:=1 to 52 do if f[i-1,j,k]=1 then f[i,j,k]:=1；

if i<=n then

begin if j<m then ohzw(i,j+1) else ohzw(i+1,1)；end；

for jj:=1 to m do

for kk:=1 to 52 do

if f[n,j,k]=1 then inc(shu[j])；

for j:=1 to m do if shu[j]>max then max:=shu[j]；

for j:=1 to m do shu[j]:=0；

end；

begin

read(n,m)；

for i:=1 to n do

begin

readln；

for j:=1 to m do

begin

read(x)；

if ord(x)-ord(’a’)>=0 then a[i,j]:=ord(x)-ord(’a’)+27 else a[i,j]:=ord(x)-ord(’A’)+1；

end；

{ for i:=1 to n do

begin

writeln；

for j:=1 to m do

write(a[i,j])；

end；

writeln；}

for i:=1 to n do

for j:=1 to m do f[i,j,a[i,j]]:=1；

ohzw(2,1)；

for j:=1 to m do

for k:=1 to 52 do

if f[n,j,k]=1 then inc(shu[j])；

for j:=1 to m do if shu[j]>max then max:=shu[j]；

write(max)；

{ for i:=1 to n do

for j:=1 to m do

for k:=1 to 52 do

if f[i,j,k]=1 then inc(shu[i,j])；

for i:=1 to n do

begin

writeln；

for j:=1 to m do

write(shu[i,j])；

end； }

end.

#1 xxwzy@2009-03-01 20:23:00

回复删除

请问大牛们怎么过的？

搜索＋剪枝？

动归＋剪枝？

动归+cheat?

还是……￥＃◎＃￥……？

#2 xxwzy@2009-03-02 03:50:00

回复删除

人呢^^…………^^

#3 xxwzy@2009-03-06 05:25:00

回复删除

人工置顶

#4 85561642@2009-03-06 05:48:00

回复删除

......................................

#5 xxwzy@2009-03-06 06:28:00

回复删除

事实证明：贪搜过不了

#6 xxwzy@2009-03-06 06:29:00

回复删除

var i1,i2,i3,h1,h2,h3,i,j,k,n,m,max:longint；

a:array[-1..1001,-1..1001]of longint；

hou,f:array[-1..1001,-1..1001,-1..101]of longint；

shu:array[-100..1001]of longint；

x:char；

begin

read(n,m)；

for i:=1 to n do

begin

readln；

for j:=1 to m do

begin

read(x)；

if ord(x)-ord(’a’)>=0 then a[i,j]:=ord(x)-ord(’a’)+27 else a[i,j]:=ord(x)-ord(’A’)+1；

end；

for i:=1 to n do

for j:=1 to m do f[i,j,a[i,j]]:=1；

for i:=n-1 downto 1 do

for j:=m-1 downto 1 do

for k:=1 to 52 do

if (a[i+1,j-1]=1)or(a[i+1,j]=1)or(a[i+1,j+1]=1) then hou[i,j,k]:=1；

for i:=2 to n do

for j:=1 to m do

begin

i1:=0；

i2:=0；

i3:=0；

for k:=1 to 52 do

if (k<>a[i,j])then

begin

if (f[i-1,j,k] = 1) then inc(i1) else if (hou[i-1,j,k] = 1) then inc(h1)；

if (f[i-1,j-1,k] = 1) then inc(i2) else if (hou[i-1,j-1,k]=1) then inc(h2)；

if (f[i-1,j+1,k] = 1) then inc(i3) else if (hou[i-1,j+1,k]=1) then inc(h3)；

end；

if (i1>i2)and(i1>i3) then

begin

for k:=1 to 52 do if f[i-1,j,k] = 1 then f[i,j,k]:=1；

continue；

end；

if (i3>i2)and(i3>i1) then

begin

for k:=1 to 52 do if f[i-1,j+1,k]=1 then f[i,j,k]:=1；

continue；

end；

if (i2>i1)and(i2>i3) then

begin

for k:=1 to 52 do if f[i-1,j-1,k]=1 then f[i,j,k]:=1；

continue；

end；

if (i1=i2)and(i2=i3) then

begin

if (h1>=i2)and(h1>=i3) then

begin

for k:=1 to 52 do if f[i-1,j,k] = 1 then f[i,j,k]:=1；

continue；

end；

if (h3>=h2)and(h3>=h1) then

begin

for k:=1 to 52 do if f[i-1,j+1,k]=1 then f[i,j,k]:=1；

continue；

end；

if (h2>=h1)and(h2>=h3) then

begin

for k:=1 to 52 do if f[i-1,j-1,k]=1 then f[i,j,k]:=1；

continue；

end；

if i1=i2 then

begin

if h1<h2 then

begin

for k:=1 to 52 do if f[i-1,j-1,k]=1 then f[i,j,k]:=1；

continue；

end

else

begin

for k:=1 to 52 do if f[i-1,j,k] = 1 then f[i,j,k]:=1；

continue；

end；

if i3=i2 then

begin

if h3<h2 then

begin

for k:=1 to 52 do if f[i-1,j+1,k]=1 then f[i,j,k]:=1；

continue；

end

else

begin

for k:=1 to 52 do if f[i-1,j,k] = 1 then f[i,j,k]:=1；

continue；

end；

if i3=i1 then

begin

if h3<h1 then

begin

for k:=1 to 52 do if f[i-1,j+1,k]=1 then f[i,j,k]:=1；

continue；

end

else

begin

for k:=1 to 52 do if f[i-1,j-1,k]=1 then f[i,j,k]:=1；

continue；

end

end；

for j:=1 to m do

for k:=1 to 52 do

if f[n,j,k]=1 then inc(shu[j])；

for j:=1 to m do if shu[j]>max then max:=shu[j]；

write(max)；

end.

超长bt程序，贪搜，过不了……％＃……