题解 - Vijos

1

Lifi LV 10 @ 2019-09-13 20:37:36

改一下题，树的高度为0，1，2.
则DP【i】【j】【0】为第i棵树高度为j时且前一棵树比i矮的最大值。
同理DP【i】【j】【1】为第i棵树高度为j时且前一棵树比i高的最大值。
第一个位置单独拿出来做成环条件判断。

#include <iostream>
#define LL long long

using namespace std;

int n;
LL dp[100005][3][2]={0};

int main()
{
    int i;
    LL ans=0;
    cin>>n;
    int a0,b0,c0,a,b,c;
    cin>>a0>>b0>>c0;
    for(i=1;i<n;i++)
    {
        cin>>a>>b>>c;
        dp[i][0][1]=max(dp[i-1][1][0],dp[i-1][2][0])+a;
        dp[i][1][0]=dp[i-1][0][1]+b;
        dp[i][1][1]=dp[i-1][2][0]+b;
        dp[i][2][0]=max(dp[i-1][0][1],dp[i-1][1][1])+c;
    }
    ans=max(ans,dp[n-1][0][1]+max(b0,c0));
    ans=max(ans,dp[n-1][1][0]+a0);
    ans=max(ans,dp[n-1][1][1]+c0);
    ans=max(ans,dp[n-1][2][0]+max(a0,b0));
    cout<<ans<<endl;
    return 0;
}

1

GUODX LV 4 @ 2018-08-19 21:47:49

来一份记忆化搜索［思维难度超低的～］

#include<bits/stdc++.h>
#define _ 100008
#define R register
using namespace std;
int n,val[4][_],f[_][4][4][2],tp[_],tot;
int dfs(R int dr,R int lst,R int one,R int up){
    if(f[dr][lst][one][up]!=-1)
        return f[dr][lst][one][up];
    if(dr==n+1){
        return ((up&&lst>one)||((!up)&&lst<one))?0:-1;
    }
    R int r=-1;
    if(dr==1){
        for(R int i=1;i<=3;i++){
            int c=dfs(dr+1,i,i,0);
            if(c!=-1)
                r=max(r,c+val[i][dr]);
        }
    }
    else{
        if(dr==2){
            for(R int i=lst+1;i<=3;i++){
                int c=dfs(dr+1,i,one,1);
                if(c!=-1)
                    r=max(r,c+val[i][dr]);
            }
            for(R int i=lst-1;i>=1;i--){
                int c=dfs(dr+1,i,one,0);
                if(c!=-1)
                    r=max(r,c+val[i][dr]);
            }
        }
        else{
            if(up){         
                for(R int i=lst-1;i>=1;i--){
                    int c=dfs(dr+1,i,one,0);
                if(c!=-1)
                    r=max(r,c+val[i][dr]);
                }
            }
            else{
                for(R int i=lst+1;i<=3;i++){
                    int c=dfs(dr+1,i,one,1);
                    if(c!=-1)
                        r=max(r,c+val[i][dr]);
                }
            }
        }
    }
    //if(dr==4)
//  cout<<dr<<' '<<lst<<' '<<one<<' '<<r<<' '<<endl;
    return f[dr][lst][one][up]=r;
}
int main(){
    cin>>n;memset(f,-1,sizeof(f));
    for(int i=1;i<=n;i++)scanf("%d%d%d",&val[1][i],&val[2][i],&val[3][i]);
    cout<<dfs(1,0,0,0);
}

1

Fop_zz LV 10 @ 2017-05-26 09:07:23

0.1s过全部。。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <cstring>
#include <ctime>
#include <vector>
#define inf 1e9
#define ll long long
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Dow(i,j,k) for(int i=k;i>=j;i--)
using namespace std;
int f[200001][5][2],n,v1[200001],v2[200001],v3[200001],ans=0;
int main()
{
    scanf("%d",&n);
    For(i,1,n)  scanf("%d%d%d",&v1[i],&v2[i],&v3[i]);
    For(i,2,n)  
    {
        f[i][1][1]=max(f[i-1][2][0]+v1[i],f[i-1][3][0]+v1[i]);
        f[i][3][0]=max(f[i-1][2][1]+v3[i],f[i-1][1][1]+v3[i]);
        f[i][2][0]=f[i-1][1][1]+v2[i];
        f[i][2][1]=f[i-1][3][0]+v2[i];
    }
    ans=max(ans,f[n][1][1]+v2[1]);ans=max(ans,f[n][3][0]+v2[1]);
    ans=max(ans,max(f[n][2][0]+v1[1],f[n][3][0]+v1[1]));
    ans=max(ans,max(f[n][2][1]+v3[1],f[n][1][1]+v3[1]));
    printf("%d",ans);
}

0

ljt12138 LV 10 @ 2016-08-23 20:55:46

没看见**环**导致WA并RP--的路过
贴一份带缩进代码
```c++
#include <bits/stdc++.h>
using namespace std;

int a[100005][4], n;
int g[100005][4][4], f[100005][4][4];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &a[i][1], &a[i][2], &a[i][3]);
memset(g, 0, sizeof g);
memset(f, 0, sizeof f);
for (int j = 1; j <= 3; j++) {
f[1][j][j] = a[1][j];
g[1][j][j] = a[1][j];
}
for (int i = 2; i <= n; i++)
for (int j = 1; j <= 3; j++) {
for (int k = 1; k <= 3; k++)
for (int l = 1; l <= 3; l++) {
if (j > k) f[i][j][l] = max(f[i][j][l], g[i-1][k][l]+a[i][j]);
if (j < k) g[i][j][l] = max(g[i][j][l], f[i-1][k][l]+a[i][j]);
}
}
int ans = 0;
for (int i = 1; i <= 3; i++)
for (int b = 1; b <= 3; b++){
if (b > i) ans = max(ans, g[n][i][b]);
if (b < i) ans = max(ans, f[n][i][b]);
}
cout << ans << endl;
return 0;
}
```

0

chonglou LV 7 @ 2012-10-27 08:38:30

编译通过...

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

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

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

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

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

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

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

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

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

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

啦啦啦呵呵呵

0

Veili LV 9 @ 2009-11-09 14:57:33

模子很多，就不要晒着相同的了。。

0

fjlyzpcr LV 8 @ 2009-11-09 14:01:39

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program ex;

var i,j,n,ans:longint;

a:Array[1..100000,1..3]of longint;

f:Array[1..100000,1..4]of longint;

mark:array[0..1,1..4]of longint;

procedure init;

var i,j:longint;

begin

readln(n);

for i:=1 to n do readln(a,a,a);

end;

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

begin

if a>b then exit(a) else exit(b);

end;

procedure dp(x:longint);

var i,j,k:longint;

begin

for i:=1 to 4 do

f[1,i]:=-maxlongint;

f[1,x]:=a[1,x div 2+1];

for i:=2 to n do

begin

{1} f:=max(f,f)+a;

{2.1} f:=f+a;

{2.2} f:=f+a;

{3} f:=max(f,f)+a;

end;

end;

procedure main;

var i,j:longint;

begin

ans:=0;

dp(1);

ans:=max(f[n,2],f[n,4]);

dp(2);

ans:=max(ans,f[n,1]);

dp(3);

ans:=max(ans,f[n,4]);

dp(4);

ans:=max(ans,max(f[n,1],f[n,3]));

end;

procedure print;

var i,j:longint;

begin

writeln(ans);

end;

begin

init;

main;

print;

end.

0

honghaijie LV 9 @ 2009-10-31 20:13:15

还要环的唉..

用f表示

种第i颗树最后一颗高度是j(j=1,2,3)

k=0表示第i棵树比i-1棵低 k=1表示第i棵树比i-1棵高

第一棵树高度是l（要环的啊啊啊）

var i,j,k,l,m,n,ans:longint;

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

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

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

begin

if a>b then max:=a else max:=b;

end;

begin

readln(n);

readln(a[1,1],a[1,2],a[1,3]);

f[1,1,0,1]:=a[1,1]; f[1,2,0,2]:=a[1,2]; f[1,2,1,2]:=a[1,2]; f[1,3,1,3]:=a[1,3];

for i:=2 to n do

begin

readln(a,a,a);

for j:=1 to 3 do

begin

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

f:=f+a;

f:=f+a;

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

end;

end;

if f[n,1,0,2]>ans then ans:=f[n,1,0,2];

if f[n,1,0,3]>ans then ans:=f[n,1,0,3];

if f[n,2,0,3]>ans then ans:=f[n,2,0,3];

if f[n,2,1,1]>ans then ans:=f[n,2,1,1];

if f[n,3,1,1]>ans then ans:=f[n,3,1,1];

if f[n,3,1,2]>ans then ans:=f[n,3,1,2];

writeln(ans);

end.

30行的..

嘿嘿

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

yzl609271536 LV 10 @ 2009-10-22 16:53:51

编译通过...

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

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

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

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

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

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

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

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

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

他居然说我过了

郁闷就当过了。。。

0

陈亮宇 LV 10 @ 2009-10-22 16:23:25

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一次AC 感觉很不错

嘿嘿

0

claire_ LV 10 @ 2009-09-13 20:19:18

膜拜voyagec2的解法，我稍稍概括了下，39行，0ms

0

Melody1992 LV 10 @ 2009-09-06 13:54:18

Var

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

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

N:longint;

Procedure Init;

Var

I:longint;

Begin

Readln(N);

For i:=1 to N do readln(a,a,a);

End;

Procedure Dp;

Var

I,Ans:longint;

Begin

F[1,1,0]:=A[1,1];

F[1,2,0]:=A[1,2];

F[1,2,1]:=A[1,2];

F[1,3,1]:=A[1,3];

H[1,1,0]:=1;

H[1,2,0]:=2;

H[1,2,1]:=2;

H[1,3,1]:=3;

For i:=2 to N do

Begin

If F>F then

Begin

F:=F+A;

H:=H;

End

Else

Begin

F:=F+A;

H:=H;

End;

F:=F+A;

H:=H;

F:=F+A;

H:=H;

If F>F then

Begin

F:=F+A;

H:=H;

End

Else

Begin

F:=F+A;

H:=H;

End;

End;

Ans:=0;

If (F[N,1,0]>Ans) and (H[N,1,0]>1) then Ans:=F[N,1,0];

If (F[N,2,0]>Ans) and (H[N,2,0]>2) then Ans:=F[N,2,0];

If (F[N,2,1]>Ans) and (H[N,2,1]Ans) and (H[N,3,1]

0

how LV 10 @ 2009-07-31 18:23:58

明摆的DP....怎么是其他类的....

0

oimaster LV 10 @ 2009-06-02 07:59:27

为了方便，把程序的常数的写的有点大了……

6k上挂了，puppy来了就AC了，但没秒闪……

0

飘の★ LV 10 @ 2009-05-15 23:21:25

方程：

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

f:=f+a;

f:=f+a;

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

0

hermitking LV 3 @ 2008-11-13 10:17:59

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

freefly LV 10 @ 2008-11-12 20:30:34

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

v:array[1..100000,1..3]of int64;

dp:array[1..100000,-2..3]of int64;

i,j,k,n:longint;

ans:int64;

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

begin

if a>b then max:=a

else max:=b;

end;

begin

readln(n);

for i:=1 to n do

begin

readln(v[i][1],v[i][2],v[i][3]);

end;

fillchar(dp,sizeof(dp),0);

for i:=2 to n do

begin

if i=2 then

begin

// 1

dp:=v[1,1]+v[2,2];

dp:=v[1,1]+v[2,3];

end

else

begin

dp:=max(dp+v,dp+v);

dp:=max(dp+v,dp+v);

dp:=dp+v;

dp:=dp+v;

end;

end;

ans:=max(dp[n,2],dp[n,3]);

fillchar(dp,sizeof(dp),0);

for i:=2 to n do

begin

if i=2 then

begin

// 2

dp:=v[1,2]+v[2,1];

dp:=v[1,2]+v[2,3];

end

else

begin

dp:=max(dp+v,dp+v);

dp:=max(dp+v,dp+v);

dp:=dp+v;

dp:=dp+v;

end;

end;

if max(dp[n,-1],dp[n,3])>ans then ans:=max(dp[n,-1],dp[n,3]);

fillchar(dp,sizeof(dp),0);

for i:=2 to n do

begin

if i=2 then

begin

// 3

dp:=v[1,3]+v[2,2];

dp:=v[1,3]+v[2,1];

end

else

begin

dp:=max(dp+v,dp+v);

dp:=max(dp+v,dp+v);

dp:=dp+v;

dp:=dp+v;

end;

end;

if max(dp[n,-1],dp[n,-2])>ans then ans:=max(dp[n,-1],dp[n,-2]);

write(ans);

end.

0

原始鸭 LV 3 @ 2008-11-11 17:02:42

看了题解才做出来的，不错的题啊，。虽然开始就往递推的方向想，但始终没能想出来，因为不会处理环状结构这个问题。。。

我是按 voyagec2 的方法写的。0S搞定

0

zhao12 LV 8 @ 2008-11-11 16:27:09

第一次tle了4个。。。发现自己打错。。做了n次动规。。改成4，全0...

0

xinlu201 LV 3 @ 2008-11-11 14:49:47

编译通过...

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

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

├ 测试数据 03：运行超时...

├ 测试数据 04：运行超时...

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行时错误...| 错误号: 202 | 堆栈溢出错

├ 测试数据 08：运行时错误...| 错误号: 202 | 堆栈溢出错

├ 测试数据 09：运行时错误...| 错误号: 202 | 堆栈溢出错

├ 测试数据 10：运行时错误...| 错误号: 202 | 堆栈溢出错

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

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

题解

59 条题解

教主的后花园

信息

状态

开发

支持

题解

59 条题解

教主的后花园

信息

状态

开发

支持

还没有账户？

登录