42 条题解
-
0
2mc LV 10 @ 2009-08-18 17:34:45
五维数组2x4x4x4x4的，写吧。
细节注意比如送前三份时，有些状态是取不到的。
加上puppy，过。
ps:第222人 -
0
-
0
第一次没写滚动数组，就说最后一个点空间溢出，我自己计算得出空间应该只用了20MB左右，这也会溢出啊……
请管理员贴一下Vijos的空间限制……
改成滚动数组后华丽地AC了：
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 56ms
├ 测试数据 11：答案正确... 337ms
├ 测试数据 12：答案正确... 586ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 9ms
├ 测试数据 11：答案正确... 166ms
├ 测试数据 12：答案正确... 306ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：481ms减枝减枝再减枝！！！！！
var i1,i2,j1,j2,n,k,t,k1,k2,max,l:longint;
p,q:boolean;
c:char;
s:set of 0..4;
d,e:array[0..3] of integer;
w:array[0..3,0..3,1..3] of integer;
f:array[boolean,0..3,0..3,0..3,0..3] of longint;
begin
d[0]:=0;
d[1]:=1;
d[2]:=1;
d[3]:=1;
e[0]:=1;
e[1]:=0;
e[2]:=0;
e[3]:=0;
for i1:=0 to 3 do
for i2:=0 to 3 do
for t:=1 to 3 do begin
s:=[];
w[i1,i2,t]:=0;
if i10 then begin
s:=s+[i1];
inc(w[i1,i2,t]);
end;
if (i20) and (i1i2) then begin
s:=s+[i2];
inc(w[i1,i2,t]);
end;
if not (t in s) then inc(w[i1,i2,t]);
end;
p:=true;
q:=false;
for i1:=0 to 3 do
for i2:=0 to 3 do
for j1:=0 to 3 do
for j2:=0 to 3 do
f[p,i1,i2,j1,j2]:=-maxlongint;
f[p,0,0,0,0]:=0;
readln(n);
for k:=1 to n do begin
for i1:=0 to 3 do
for i2:=d[i1] to 3 do begin
if k>4 then l:=e[i1] else l:=0;
for j1:=l to 3 do
for j2:=d[j1] to 3 do
f[q,i1,i2,j1,j2]:=-maxlongint;
end;
read(c);
case c of
'M':t:=1;
'B':t:=2;
'F':t:=3;
end;
for i1:=0 to 3 do
for i2:=d[i1] to 3 do begin
if k>4 then l:=e[i1] else l:=0;
for j1:=l to 3 do
for j2:=d[j1] to 3 do
if f[p,i1,i2,j1,j2]>-maxlongint then begin
if f[p,i1,i2,j1,j2]+w[i1,i2,t]>f[q,i2,t,j1,j2] then
f[q,i2,t,j1,j2]:=f[p,i1,i2,j1,j2]+w[i1,i2,t];
if f[p,i1,i2,j1,j2]+w[j1,j2,t]>f[q,i1,i2,j2,t] then
f[q,i1,i2,j2,t]:=f[p,i1,i2,j1,j2]+w[j1,j2,t];
end;
end;
p:=q;
q:=not q;
end;
max:=0;
for i1:=0 to 3 do
for i2:=0 to 3 do
for j1:=0 to 3 do
for j2:=0 to 3 do
if f[p,i1,i2,j1,j2]>max then
max:=f[p,i1,i2,j1,j2];
writeln(max);
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 25ms
├ 测试数据 10：答案正确... 197ms
├ 测试数据 11：答案正确... 759ms
├ 测试数据 12：答案正确... 1166ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：2147ms
太慢了!主体算法是动态规划:
f表示选取第i辆车后第一个矿的最后运到的两个车分别是x1,x2,第二个矿的最后运到的两个车分别是x3,x4的最大产矿数.
f=max(f,f)
{f或f可以到达,即合法,若两个状态都不合法,则f也不合法}注:
1.a[i]可以用数值来表示,例如M为1,F为2,B为3;
2.因为f[i]的值只与f有关,所以可以利用滚动数组进行优化;
3.细节问题要注意,状态要注意是否合法. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 118ms
├ 测试数据 11：答案正确... 462ms
├ 测试数据 12：答案正确... 742ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：1322ms过得超猥琐，用的四维数组。
-
0
fammiebright LV 9 @ 2008-11-06 11:49:39
不会状态压缩。用的true1023的方法。
还有就是注意前两天的情况。 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 56ms
├ 测试数据 11：答案正确... 291ms
├ 测试数据 12：答案正确... 556ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：903ms
第99个
不用状态压缩也可以这么快...
f表示选了第i个后,矿井1最后两个元素为a,b,矿井2为a1,b1;
f:=max{f+d[x,a,s[i]]}
f:=max{f+d[x,a1,s[i]} (x为三种配餐的任意一种)
这里d数组是判断a,b,c三个元素组合后的产矿数量.
我是用的递推....严格说也不算,就是知道f的时候就推出f[i],一步一步就出来了...没想到还不慢,哈哈!
这题还可以用状态压缩的DP,详见ioi2007的题解
2mc
LV 10
@ 2009-08-18 17:34:45
