{
丑陋的程序，丑陋的时间，好在比较短。。。
}
var
f:array[0..100,0..100,1..3] of longint;
a:array[1..100,1..3] of longint;
i,j,k,n,m,ans,ii:longint;
function max(x,y:longint):longint;
begin
if x>y then max:=x
else max:=y;
end;
function c(x:longint):longint;
begin
if x=1 then c:=2;
if x=2 then c:=3;
if x=3 then c:=1;
end;
function d(x:longint):longint;
begin
d:=c(c(x));
end;
begin
readln(n,m);
for i:=1 to n do
readln(a[i,1],a[i,2],a[i,3]);
for i:=1 to n do
for j:=1 to 3 do
f[i,1,j]:=a[i,j];
for i:=1 to n do
for j:=1 to m do
for k:=1 to 3 do
begin
for ii:=1 to i-1 do
begin
f[i,j,k]:=max(f[i,j,k],f[ii,j-1,1]+a[i,k]);
f[i,j,k]:=max(f[i,j,k],f[ii,j-1,2]+a[i,k]);
f[i,j,k]:=max(f[i,j,k],f[ii,j-1,3]+a[i,k]);
if ((a[ii,1]>=a[i,c(k)])and(a[ii,2]>=a[i,d(k)]))or((a[ii,1]>=a[i,d(k)])and(a[ii,2]>=a[i,c(k)])) then
f[i,j,k]:=max(f[i,j,k],f[ii,j,3]+a[i,k]);
if ((a[ii,1]>=a[i,c(k)])and(a[ii,3]>=a[i,d(k)]))or((a[ii,1]>=a[i,d(k)])and(a[ii,3]>=a[i,c(k)])) then
f[i,j,k]:=max(f[i,j,k],f[ii,j,2]+a[i,k]);
if ((a[ii,3]>=a[i,c(k)])and(a[ii,2]>=a[i,d(k)]))or((a[ii,3]>=a[i,d(k)])and(a[ii,2]>=a[i,c(k)])) then
f[i,j,k]:=max(f[i,j,k],f[ii,j,1]+a[i,k]);
end;
ans:=max(ans,f[i,j,k]);
end;
writeln(ans);
end.

var n,m:Longint;

　　a,b,c:array[0..100] of longint;

　　bl:array[0..100,0..3] of longint;

　　f:array[0..100,0..100,0..3] of longint;

procedure init;

var i:longint;

begin

　　 readln(n,m);

　　 a[0]:=0;b[0]:=0;c[0]:=0;fillchar(bl,sizeof(bl),0);

　　 for i:=1 to n do

　　　　 begin

　　　　　　 readln(a[i],b[i],c[i]);

　　　　　　 block:=c[i];

　　　　　　 block:=a[i];

　　　　　　 block:=b[i];

　　　　 end;

end;

function max(a,b:longint):longint;

begin

　　 if a=x2)and(y1>=y2))or((x1>=y2)and(y1>=x2)) then exit(true) else exit(false);

end;

procedure find;

var i,j,t,k,p,h:longint;

begin

　　 f[1,1,1]:=bl[1,1];f[1,1,2]:=bl[1,2];f[1,1,3]:=bl[1,3];

　　 for i:=2 to n do

　　　　 for p:=1 to i-1 do

　　　　　　 for j:=1 to i do

　　　　　　　　 for k:=1 to 3 do

　　　　　　　　　　 for h:=1 to 3 do

　　　　　　　　　　　　 begin

　　　　　　　　　　　　　　 if ok(p,h,i,k) then

　　　　　　　　　　　　　　　　 begin

　　　　　　　　　　　　　　　　　　 f:=max(f[p,j,h]+bl,f);

　　　　　　　　　　　　　　　　　　 t:=f;

　　　　　　　　　　　　　　　　 end;

　　　　　　　　　　　　　　 f:=max(f[p,j-1,h]+bl,f);

　　　　　　　　　　　　　　 t:=f;

　　　　　　　　　　　　 end;

　　 t:=0;

　　 for i:=m to n do

　　　　 for j:=1 to 3 do t:=max(t,f);

　　 writeln(t);

end;

begin

　　 init;

　　 find;

end.

DP

---|---|---|---|---|---|---|---|---|---|---|--

编译通过...

├ 测试数据 01：答案正确... 25ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：128ms

var n,m:Longint;

a,b,c:array[0..100]of longint;

block:array[0..100,0..3]of longint;

f:array[0..100,0..100,0..3]of longint;

procedure init;

var i:longint;

begin

readln(n,m);

a[0]:=0;b[0]:=0;c[0]:=0;fillchar(block,sizeof(block),0);

for i:=1 to n do

begin

readln(a[i],b[i],c[i]);

block:=c[i];

block:=a[i];

block:=b[i];

end;

end;

function max(a,b:longint):longint;

begin

if a=x2)and(y1>=y2))or((x1>=y2)and(y1>=x2)) then exit(true) else exit(false);

end;

procedure find;

var i,j,t,k,p,h:longint;

begin

fillchar(f,sizeof(f),0);

{for i:=1 to m do

for k:=1 to 3 do

for p:=1 to 3 do

f:=max(f,f+block);

}

f[1,1,1]:=block[1,1];f[1,1,2]:=block[1,2];f[1,1,3]:=block[1,3];

for i:=2 to n do

for p:=1 to i-1 do

for j:=1 to i do

for k:=1 to 3 do

for h:=1 to 3 do

begin

if ok(p,h,i,k) then

begin

f:=max(f[p,j,h]+block,f);

t:=f;

end;

f:=max(f[p,j-1,h]+block,f);

t:=f;

end;

t:=0;

for i:=m to n do

for j:=1 to 3 do t:=max(t,f);

writeln(t);

end;

begin

init;

find;

end.

Flag 　　 Accepted

题号 　　P1464

类型(?) 　　动态规划

通过 　　52人

提交 　　125次

通过率 　　42%

难度 　　2

提交 讨论 题解

判边长少写了个等号,悲惨地多交了三次呀...

这也忒牛了，这哪是97年的题啊...

本题是最近才添加的

97年NOI第二试试题的说

分类放错地方的说

本题的解法可以参考lrj的黑书P119

新题目，诧异了，为什么现在才发现？

1次AC，爽~~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

这不是NOIp97的题目吧？

dpdpdpdpdpdpdpdpdpdpdddp!!!!!!

好隐蔽的题目

bs楼下，粘代码……

一次AC 哈哈 爽！！

双重DP，O（n^3+n*n*m）

我擦- -一个疏忽让我没能一次AC。。。

注意最后打的是全部dp数组里的最大值- -

不是dp【m,n,k】(k=1..3)的最大值。。。。

方程好写---|

if (f[j,t,k,kk]) then

dp[j,i,k]:=max(dp[j,i,k],max(dp[t,i-1,kk],dp[t,i,kk])+a[j,k])

else

dp[j,i,k]:=max(dp[j,i,k],dp[t,i-1,kk]+a[j,k]);

难写的是比较上一个能不能包含此个的那段代码。。。

var

ans,m,n,ka,kb,kka,kkb,j,i,k,kk,t:longint;

f:array[0..100,0..100,1..3,1..3]of boolean;

a:array[0..100,1..3]of longint;

dp:array[0..100,0..100,1..3]of longint;

function max(p,g:longint):longint;

begin

if p>g then exit(p) else exit(g);

end;

begin

read(m,n);

for i:=1 to m do

begin

for j:=1 to 3 do

read(a);

end;

for j:=2 to m do

for t:=1 to j-1 do

for k:=1 to 3 do

for kk:=1 to 3 do

begin

case k of

1:begin ka:=a[j,2]; kb:=a[j,3]; end;

2:begin ka:=a[j,1]; kb:=a[j,3]; end;

3:begin ka:=a[j,1]; kb:=a[j,2]; end;

end;

case kk of

1:begin kka:=a[t,2]; kkb:=a[t,3]; end;

2:begin kka:=a[t,1]; kkb:=a[t,3]; end;

3:begin kka:=a[t,1]; kkb:=a[t,2]; end;

end;

if (((ka

├ 测试数据 01：答案正确... 88ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：88ms

弱弱的DP.. 88ms..

犯低级错误了~~~

蛮简单的一道DP

F

表示前I跟柱子分成J组,最后一跟柱子是以第I跟柱子以第K条边做高的最大值

F:=MAX(F[1..I-1,J-1,1..3],F[1..I-1,J,1..3](a

怎么还不通过？？

地板

抢不过你们~~

hehe

Orz= =

bandeng