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

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

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

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

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

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

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

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

第五个点为什么被wa??????????

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program garden;

var n,final:longint;

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

w:array[0..100000,1..3]of integer;

procedure init;

var i,j:longint;

begin

readln(n);

for i:=1 to n do

begin

for j:=1 to 3 do

begin

read(w);

end;

readln;

end;

end;

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

begin

if a>b then exit(a)

else exit(b);

end;

procedure dp;

var j:longint;

begin

for j:=2 to n do

begin

f[j,1,1]:=max(f[j-1,2,0]+w[j,1],f[j-1,3,0]+w[j,1]);

f[j,2,1]:=f[j-1,3,0]+w[j,2];

f[j,2,0]:=f[j-1,1,1]+w[j,2];

f[j,3,0]:=max(f[j-1,2,1]+w[j,3],f[j-1,1,1]+w[j,3]);

end;

end;

procedure outit(v:longint);

begin

if (v1) and (f[n,1,1]>final) then

final:=f[n,1,1];

if (v2) and (f[n,2,1]>final) then

final:=f[n,2,1];

if (v2) and (f[n,2,0]>final) then

final:=f[n,2,0];

if (v3) and (f[n,3,0]>final) then

final:=f[n,3,0];

end;

procedure main;

var i:longint;

begin

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

for i:=2 to n do

begin

f:=w;f:=w;

f:=w;f:=w;

end;

final:=0;

{l=1}

f[1,1,1]:=w[1,1];

dp;

outit(1);

{l=2}

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

for i:=2 to n do

begin

f:=w;f:=w;

f:=w;f:=w;

end;

f[1,2,1]:=w[1,2];

f[1,2,0]:=w[1,2];

dp;

outit(2);

{l=3}

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

for i:=2 to n do

begin

f:=w;f:=w;

f:=w;f:=w;

end;

f[1,3,0]:=w[1,3];

dp;

outit(3);

end;

procedure print;

begin

writeln(final);

end;

begin

init;

main;

print;

end.

规律不能想当然，实践，全面，考虑到特殊情况

仔细理会。。

10ac

program Ltr;

const maxn=100000;

var f:array[1..4,1..maxn,1..3] of longint;

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

mx,p,i,j,k,l,m,n:longint;

function max(x,y:longint):longint;

begin

if x>y then exit(x)

else exit(y);

end;

begin

readln(n);

for i:=1 to n do begin

for j:=1 to 3 do read(a);

readln;

end;

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

p:=1;f[1,1,1]:=a[1,1];

for i:=2 to n do begin

if f[p,i-1,1]=0 then f[p,i,1]:=max(f[p,i-1,2],f[p,i-1,3])+a;

if f[p,i-1,1]=0 then f[p,i,2]:=f[p,i-1,3]+a;

if f[p,i-1,3]=0 then f[p,i,2]:=f[p,i-1,1]+a;

if f[p,i-1,3]=0 then f[p,i,3]:=max(f[p,i-1,1],f[p,i-1,2])+a;

end;

p:=2;f[2,1,2]:=a[1,2];f[2,2,1]:=a[1,2]+a[2,1];

for i:=3 to n-1 do begin

if f[p,i-1,1]=0 then f[p,i,1]:=max(f[p,i-1,2],f[p,i-1,3])+a;

if f[p,i-1,1]=0 then f[p,i,2]:=f[p,i-1,3]+a;

if f[p,i-1,3]=0 then f[p,i,2]:=f[p,i-1,1]+a;

if f[p,i-1,3]=0 then f[p,i,3]:=max(f[p,i-1,1],f[p,i-1,2])+a;

end;

f[p,n,1]:=max(f[p,n-1,2],f[p,n-1,3])+a[n,1];

p:=3;f[3,1,2]:=a[1,2];f[3,2,3]:=a[1,2]+a[2,3];

for i:=3 to n-1 do begin

if f[p,i-1,1]=0 then f[p,i,1]:=max(f[p,i-1,2],f[p,i-1,3])+a;

if f[p,i-1,1]=0 then f[p,i,2]:=f[p,i-1,3]+a;

if f[p,i-1,3]=0 then f[p,i,2]:=f[p,i-1,1]+a;

if f[p,i-1,3]=0 then f[p,i,3]:=max(f[p,i-1,1],f[p,i-1,2])+a;

end;

f[p,n,3]:=max(f[p,n-1,1],f[p,n-1,2])+a[n,3];

p:=4;f[4,1,3]:=a[1,3];

for i:=2 to n do begin

if f[p,i-1,1]=0 then f[p,i,1]:=max(f[p,i-1,2],f[p,i-1,3])+a;

if f[p,i-1,1]=0 then f[p,i,2]:=f[p,i-1,3]+a;

if f[p,i-1,3]=0 then f[p,i,2]:=f[p,i-1,1]+a;

if f[p,i-1,3]=0 then f[p,i,3]:=max(f[p,i-1,1],f[p,i-1,2])+a;

end;

mx:=0;

for i:=1 to 4 do

for j:=1 to 3 do

if f>mx then mx:=f;

writeln(mx);

end.

第五个点过不了.....

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

下午在小号上还是全0的，RP啊。。。

只说一下状态

f 表示对于第i个位置，种植第j种树，且保证比左边低(0)，或者比左边高（1）时所能获得的最大值，至于状态转移是很容易写出来的

至于对环的处理，很简单，就是对于i=1的所有状态的值初始化为0，也就是先不种树，往后退，最后在找答案的时候根据n的情况加上1处的树，比较输出即可

我的程序第五个点不过，

只得90分；

用循环的dp

只开了

max,n,i,j,k,q:longint;

s:array[1..2,1..3] of longint;

b1,b2,dp1,dp2:array[1..3,1..3] of longint;

---| 第1题 ---|---|---|---|---|---|---|---|---|---|---|--

编译通过...

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

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

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

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

测试数据05：答案错误...　

├ 标准行输出3153276

错误行输出 3152972

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

终于。。

题解里的方法确实不错。。

比赛的时候就在忧虑 怎么来记录 1号的高度（愁）

4次DP（分别种在1号位10 20 30，其中20有两种情况，种了20后一个是30，后者后一个是10），取出所有的max即可，注意变量的关系之类的。（有点递推的意思）。。

赞！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

水题

编译通过...

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

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

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

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

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

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

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

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

Unaccepted 有效得分：90 有效耗时：0ms

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

谁知道第5个数据啊!!!!

我的rp阿....

因为没参加模拟赛 .....我们班一 牡牛 拿这道题来问我...

他...竟然没跟我说树要同时高或低...只说不同....

出于对同班兼同宿舍的情面上....

我相信了他的话....结果连题目都没看就写了.....

第一次只过两个点....于是我检查阿检查...都没错...回去看一下原题...我才发现！！！！！！！！！！！！！！

咳...把程序改了一下就AC了.....

PS：我用动规解的.....不过秒杀不了...可能没加优化的缘故...

iostream超4个

第4题在1422

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

换成PUPPY后就成了这样……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

感谢LS的LS的LS的大牛~

简单的二维dp

复杂度O（n）

递推递推~~

刚开始觉得太简单，于是敲程序时把环形这条件给忘记了。

处理环形只要在线性递推得基础上记录第一棵树的上下趋势和高度即可。

为使DP的思路清晰一些，建议分情况讨论：

第一种情况为第一棵树高度为10（F[1，1]：=A[1，1]；）

当I为奇时F：=F+A；F：=MAX（F，F）+A

当I为偶时F：=F+A；F：=MAX（F，F+A；

1 1

1 1 1 ……

如图：I为奇时，树要比它旁边两棵来的矮

这种情况下最后一棵树的高度必须是20或30，ANS：=MAX（F[N，2]，F[N，3]）；

第二种情况是第一棵树高为30 最后一棵高度为10或20

第三种情况是第一棵树高为20，最后一棵高度为10；

第四种情况是第一棵树高为20，最后一棵高度为30；

每步程序雷同，直接COPY稍做修改

完全可以用3维代替

F表示考虑第I棵树时，种了高度为J的树，这种状态的第一棵树高度为K

比赛时我就这么写。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

个人觉得用递推写起来会方便一点,我用F表示前I棵树,最后一棵种J种树,前一棵比这一棵矮(0)或高(1);手动枚举前两棵树.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

写的太猥琐了。。满屏幕的if max..

3维DP 83lines