 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
不会构造，于是直接状压DP打表。附代码及解题报告。状态的表示：状态只与前两行的宝石有关。最朴素的表示就4^(2n)次方的了，暴力转移的话，n=7转移一行
大约需要4^14*4^7次，严重不可接受。
但我们发现，很多状态表示是无用的。例如当前行某一列是diamond，但diamond根本不关心前一行这一
列的值，为何需要用4个状态表示它？于是优化每一格状态表示到10种：（a-b表示某列当前行是a，上一
行是b）
0=ruby-emerald 1=ruby-sapphire 2=ruby-diamond 3=ruby-other
4=emerald-sapphire 5=emerald-diamond 6=emerald-other
7=sapphire-diamond 8=sapphire-other
9=diamond-other
这样状态最多只有10^7种了。这样代码跑个一两天也是可以跑完的。但我们还可以优化。
我们发现很多状态根本不能用，例如如果有这种情况
?R?
RRE
这个状态中，下一行第二列无论怎么填都不能满足ruby的要求，完全可以舍弃。这个过程可以在10^7*7
时间内完成。我们发现这时n=7时状态只有不到200万种了（还是20万？记不清了）。
然后，转移也可以优化。例如这个状态
?R?
SRE
这个状态中，第二列只能填diamond。于是可以先把那些列可以填那些处理出来，可以极大地加快运行速
度。我试验了一下，这时n=7时每一行只要转移不到6亿次。这样代码就可以在一个小时左右把表打完了。
打表用代码：
var
a,b,cc:array[0..11] of longint;
s:array[0..11] of set of byte;
dt:array[0..11,0..11] of longint;
d:array[0..10000000] of longint;
ok:array[0..10000000] of longint;
dp:array[1..7,0..2000000] of longint;
function checkinit(n,x1:longint):boolean;
var i:longint;
begin for i:=1 to n do
begin a[i]:=x1 mod 10;
x1:=x1 div 10;
if not (a[i] in [3,6,8,9]) then exit(false);
end;
exit(true);
end;
function checkvl(n,x1:longint):longint;
var i,res:longint;
begin res:=0;
for i:=1 to n do
begin a[i]:=x1 mod 10;
x1:=x1 div 10;
if a[i] in [0,1,2,3] then inc(res);
end;
exit(res);
end;
function check(n,x1:longint):boolean;
var i,x,y:longint;
begin for i:=1 to n do
begin a[i]:=x1 mod 10;
x1:=x1 div 10;
end;
case a[1] of
0: if a[2] in [0,1,2,3,4,5,6] then exit(false);
1: if a[2] in [0,1,2,3,7,8] then exit(false);
2: if a[2] in [0,1,2,3,9] then exit(false);
3: exit(false);
6: if a[2] in [0,1,2,3,4,5,6] then exit(false);
end;
case a[n] of
0: if a[n-1] in [0,1,2,3,4,5,6] then exit(false);
1: if a[n-1] in [0,1,2,3,7,8] then exit(false);
2: if a[n-1] in [0,1,2,3,9] then exit(false);
3: exit(false);
6: if a[n-1] in [0,1,2,3,4,5,6] then exit(false);
end;
for i:=2 to n-1 do
case a[i] of
0: begin
if a[i-1] in [7,8,9] then continue;
if a[i+1] in [7,8,9] then continue;
exit(false);
end;
1: begin
if a[i-1] in [4,5,6,9] then continue;
if a[i+1] in [4,5,6,9] then continue;
exit(false);
end;
2: begin
if a[i-1] in [4,5,6,7,8] then continue;
if a[i+1] in [4,5,6,7,8] then continue;
exit(false);
end;
3: begin
if a[i-1] in [0,1,2,3] then exit(false);
if a[i+1] in [0,1,2,3] then exit(false);
if a[i-1] in [4,5,6] then x:=2;
if a[i-1] in [7,8] then x:=3;
if a[i-1]=9 then x:=4;
if a[i+1] in [4,5,6] then y:=2;
if a[i+1] in [7,8] then y:=3;
if a[i+1]=9 then y:=4;
if x=y then exit(false);
end;
6: begin
if a[i-1] in [7,8,9] then continue;
if a[i+1] in [7,8,9] then continue;
exit(false);
end;
end;
exit(true);
end;
procedure expand(n,x1,next:longint);
var i,x,y,j,cur,xw:longint;
begin xw:=x1;
for i:=1 to n do
begin a[i]:=x1 mod 10;
x1:=x1 div 10;
end;
case a[1] of
0: if a[2] in [7,8] then s[1]:=[9] else s[1]:=[8];
1: if a[2] in [4,5,6] then s[1]:=[9] else s[1]:=[6];
2: if a[2] in [4,5,6] then s[1]:=[8] else s[1]:=[6];
4: if a[2] in [0,1,2,3,4,5,6,7,8] then s[1]:=[9] else s[1]:=[0,6,8,9];
5: if a[2] in [0,1,2,3,4,5,6,9] then s[1]:=[8] else s[1]:=[0,6,8,9];
6: if a[2] in [7,8] then s[1]:=[9] else s[1]:=[8];
7: s[1]:=[1,4,8,9];
8: if a[2] in [9] then s[1]:=[1,4,8,9] else s[1]:=[9];
9: s[1]:=[2,5,7,9];
end;
case a[n] of
0: if a[n-1] in [7,8] then s[n]:=[9] else s[n]:=[8];
1: if a[n-1] in [4,5,6] then s[n]:=[9] else s[n]:=[6];
2: if a[n-1] in [4,5,6] then s[n]:=[8] else s[n]:=[6];
4: if a[n-1] in [0,1,2,3,4,5,6,7,8] then s[n]:=[9] else s[n]:=[0,6,8,9];
5: if a[n-1] in [0,1,2,3,4,5,6,9] then s[n]:=[8] else s[n]:=[0,6,8,9];
6: if a[n-1] in [7,8] then s[n]:=[9] else s[n]:=[8];
7: s[n]:=[1,4,8,9];
8: if a[n-1] in [9] then s[n]:=[1,4,8,9] else s[n]:=[9];
9: s[n]:=[2,5,7,9];
end;
for i:=2 to n-1 do
case a[i] of
0: begin
if a[i-1] in [0,1,2,3] then x:=2;
if a[i-1] in [4,5,6] then x:=2;
if a[i-1] in [7,8] then x:=3;
if a[i-1] in [9] then x:=4;
if a[i+1] in [0,1,2,3] then y:=2;
if a[i+1] in [4,5,6] then y:=2;
if a[i+1] in [7,8] then y:=3;
if a[i+1] in [9] then y:=4;
if (x+y=7) then
s[i]:=[3,6,8,9]
else if (x=3)or(y=3) then
s[i]:=[9]
else s[i]:=[8];
end;
1: begin
if a[i-1] in [0,1,2,3] then x:=2;
if a[i-1] in [4,5,6] then x:=3;
if a[i-1] in [7,8] then x:=2;
if a[i-1] in [9] then x:=4;
if a[i+1] in [0,1,2,3] then y:=2;
if a[i+1] in [4,5,6] then y:=3;
if a[i+1] in [7,8] then y:=2;
if a[i+1] in [9] then y:=4;
if (x+y=7) then
s[i]:=[3,6,8,9]
else if (x=3)or(y=3) then
s[i]:=[9]
else s[i]:=[6];
end;
2: begin
if a[i-1] in [0,1,2,3] then x:=2;
if a[i-1] in [4,5,6] then x:=3;
if a[i-1] in [7,8] then x:=4;
if a[i-1] in [9] then x:=2;
if a[i+1] in [0,1,2,3] then y:=2;
if a[i+1] in [4,5,6] then y:=3;
if a[i+1] in [7,8] then y:=4;
if a[i+1] in [9] then y:=2;
if (x+y=7) then
s[i]:=[3,6,8,9]
else if (x=3)or(y=3) then
s[i]:=[8]
else s[i]:=[6];
end;
3: begin
if a[i-1] in [4,5,6] then x:=2;
if a[i-1] in [7,8] then x:=3;
if a[i-1] in [9] then x:=4;
if a[i+1] in [4,5,6] then y:=2;
if a[i+1] in [7,8] then y:=3;
if a[i+1] in [9] then y:=4;
x:=9-x-y;
if x=2 then s[i]:=[6];
if x=3 then s[i]:=[8];
if x=4 then s[i]:=[9];
end;
4: begin
x:=0;
if a[i-1] in [9] then x:=2;
if a[i+1] in [9] then x:=2;
if x=2 then s[i]:=[0,6,8,9] else s[i]:=[9];
end;
5: begin
x:=0;
if a[i-1] in [7,8] then x:=2;
if a[i+1] in [7,8] then x:=2;
if x=2 then s[i]:=[0,6,8,9] else s[i]:=[8];
end;
6: begin
if a[i-1] in [0,1,2,3] then x:=2;
if a[i-1] in [4,5,6] then x:=2;
if a[i-1] in [7,8] then x:=3;
if a[i-1] in [9] then x:=4;
if a[i+1] in [0,1,2,3] then y:=2;
if a[i+1] in [4,5,6] then y:=2;
if a[i+1] in [7,8] then y:=3;
if a[i+1] in [9] then y:=4;
if (x+y=7) then
s[i]:=[0,6,8,9]
else if (x=3)or(y=3) then
s[i]:=[9]
else s[i]:=[8];
end;
7: s[i]:=[1,4,8,9];
8: begin
x:=0;
if a[i-1] in [9] then x:=2;
if a[i+1] in [9] then x:=2;
if x=2 then s[i]:=[1,4,8,9] else s[i]:=[9];
end;
9: s[i]:=[2,5,7,9];
end;
fillchar(cc,sizeof(cc),0);
for i:=1 to n do
for j:=0 to 9 do
if j in s[i] then
begin inc(cc[i]);
dt[i,cc[i]]:=j;
end;
for i:=1 to n do b[i]:=1;
b[0]:=0;
while b[0]=0 do
begin cur:=0;
for i:=n downto 1 do cur:=cur*10+dt[i,b[i]];
if ok[cur]<>0 then
if dp[next-1,ok[xw]]+checkvl(n,cur)>dp[next,ok[cur]] then
dp[next,ok[cur]]:=dp[next-1,ok[xw]]+checkvl(n,cur);
j:=n;
while (j>0)and(b[j]=cc[j]) do begin b[j]:=1; dec(j); end;
inc(b[j]);
end;
end;
function checklastok(n,x1:longint):boolean;
var i,x,y,j,cur,xw:longint;
begin xw:=x1;
for i:=1 to n do
begin a[i]:=x1 mod 10;
x1:=x1 div 10;
end;
case a[1] of
0: if a[2] in [7,8] then s[1]:=[9] else s[1]:=[8];
1: if a[2] in [4,5,6] then s[1]:=[9] else s[1]:=[6];
2: if a[2] in [4,5,6] then s[1]:=[8] else s[1]:=[6];
4: if a[2] in [0,1,2,3,4,5,6,7,8] then s[1]:=[9] else s[1]:=[0,6,8,9];
5: if a[2] in [0,1,2,3,4,5,6,9] then s[1]:=[8] else s[1]:=[0,6,8,9];
6: if a[2] in [7,8] then s[1]:=[9] else s[1]:=[8];
7: s[1]:=[1,4,8,9];
8: if a[2] in [9] then s[1]:=[1,4,8,9] else s[1]:=[9];
9: s[1]:=[2,5,7,9];
end;
case a[n] of
0: if a[n-1] in [7,8] then s[n]:=[9] else s[n]:=[8];
1: if a[n-1] in [4,5,6] then s[n]:=[9] else s[n]:=[6];
2: if a[n-1] in [4,5,6] then s[n]:=[8] else s[n]:=[6];
4: if a[n-1] in [0,1,2,3,4,5,6,7,8] then s[n]:=[9] else s[n]:=[0,6,8,9];
5: if a[n-1] in [0,1,2,3,4,5,6,9] then s[n]:=[8] else s[n]:=[0,6,8,9];
6: if a[n-1] in [7,8] then s[n]:=[9] else s[n]:=[8];
7: s[n]:=[1,4,8,9];
8: if a[n-1] in [9] then s[n]:=[1,4,8,9] else s[n]:=[9];
9: s[n]:=[2,5,7,9];
end;
for i:=2 to n-1 do
case a[i] of
0: begin
if a[i-1] in [0,1,2,3] then x:=2;
if a[i-1] in [4,5,6] then x:=2;
if a[i-1] in [7,8] then x:=3;
if a[i-1] in [9] then x:=4;
if a[i+1] in [0,1,2,3] then y:=2;
if a[i+1] in [4,5,6] then y:=2;
if a[i+1] in [7,8] then y:=3;
if a[i+1] in [9] then y:=4;
if (x+y=7) then
s[i]:=[3,6,8,9]
else if (x=3)or(y=3) then
s[i]:=[9]
else s[i]:=[8];
end;
1: begin
if a[i-1] in [0,1,2,3] then x:=2;
if a[i-1] in [4,5,6] then x:=3;
if a[i-1] in [7,8] then x:=2;
if a[i-1] in [9] then x:=4;
if a[i+1] in [0,1,2,3] then y:=2;
if a[i+1] in [4,5,6] then y:=3;
if a[i+1] in [7,8] then y:=2;
if a[i+1] in [9] then y:=4;
if (x+y=7) then
s[i]:=[3,6,8,9]
else if (x=3)or(y=3) then
s[i]:=[9]
else s[i]:=[6];
end;
2: begin
if a[i-1] in [0,1,2,3] then x:=2;
if a[i-1] in [4,5,6] then x:=3;
if a[i-1] in [7,8] then x:=4;
if a[i-1] in [9] then x:=2;
if a[i+1] in [0,1,2,3] then y:=2;
if a[i+1] in [4,5,6] then y:=3;
if a[i+1] in [7,8] then y:=4;
if a[i+1] in [9] then y:=2;
if (x+y=7) then
s[i]:=[3,6,8,9]
else if (x=3)or(y=3) then
s[i]:=[8]
else s[i]:=[6];
end;
3: begin
if a[i-1] in [4,5,6] then x:=2;
if a[i-1] in [7,8] then x:=3;
if a[i-1] in [9] then x:=4;
if a[i+1] in [4,5,6] then y:=2;
if a[i+1] in [7,8] then y:=3;
if a[i+1] in [9] then y:=4;
x:=9-x-y;
if x=2 then s[i]:=[6];
if x=3 then s[i]:=[8];
if x=4 then s[i]:=[9];
end;
4: begin
x:=0;
if a[i-1] in [9] then x:=2;
if a[i+1] in [9] then x:=2;
if x=2 then s[i]:=[0,6,8,9] else s[i]:=[9];
end;
5: begin
x:=0;
if a[i-1] in [7,8] then x:=2;
if a[i+1] in [7,8] then x:=2;
if x=2 then s[i]:=[0,6,8,9] else s[i]:=[8];
end;
6: begin
if a[i-1] in [0,1,2,3] then x:=2;
if a[i-1] in [4,5,6] then x:=2;
if a[i-1] in [7,8] then x:=3;
if a[i-1] in [9] then x:=4;
if a[i+1] in [0,1,2,3] then y:=2;
if a[i+1] in [4,5,6] then y:=2;
if a[i+1] in [7,8] then y:=3;
if a[i+1] in [9] then y:=4;
if (x+y=7) then
s[i]:=[0,6,8,9]
else if (x=3)or(y=3) then
s[i]:=[9]
else s[i]:=[8];
end;
7: s[i]:=[1,4,8,9];
8: begin
x:=0;
if a[i-1] in [9] then x:=2;
if a[i+1] in [9] then x:=2;
if x=2 then s[i]:=[1,4,8,9] else s[i]:=[9];
end;
9: s[i]:=[2,5,7,9];
end;
fillchar(cc,sizeof(cc),0);
for i:=1 to n do
for j:=0 to 9 do
if j in s[i] then
begin inc(cc[i]);
dt[i,cc[i]]:=j;
end;
for i:=1 to n do if cc[i]<>4 then exit(false);
exit(true);
end;
procedure solve(n:longint);
var all,i,j,count,ans:longint;
begin //0=ruby-emerald 1=ruby-sapphire 2=ruby-diamond 3=ruby-other
//4=emerald-sapphire 5=emerald-diamond 6=emerald-other
//7=sapphire-diamond 8=sapphire-other
//9=diamond-other
all:=1;
for i:=1 to n do all:=all*10;
dec(all);
fillchar(ok,sizeof(ok),0);
count:=0;
for i:=0 to all do
if check(n,i) then
begin inc(count);
d[count]:=i;
ok[i]:=count;
end;
for i:=1 to 7 do
for j:=1 to count do
dp[i,j]:=-maxlongint;
for j:=1 to count do
if checkinit(n,d[j]) then
dp[1,j]:=checkvl(n,d[j]);
for i:=2 to 7 do
for j:=1 to count do
if dp[i-1,j]<>-maxlongint then
expand(n,d[j],i);
for i:=2 to 7 do
begin ans:=-maxlongint;
for j:=1 to count do
if checklastok(n,d[j]) then
if dp[i,j]>ans then
ans:=dp[i,j];
write(ans,' ');
end;
writeln;
end;
var
i:longint;
begin
assign(output,'3861.out');
rewrite(output);
for i:=2 to 7 do solve(i);
close(output);
end.
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
