59 条题解

  • 1
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2009-11-09 14:57:33

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

  • 0
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2009-09-13 20:19:18

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

  • 0
    @ 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
    @ 2009-07-31 18:23:58

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

  • 0
    @ 2009-06-02 07:59:27

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

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

  • 0
    @ 2009-05-15 23:21:25

    方程:

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

    f:=f+a;

    f:=f+a;

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

  • 0
    @ 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
    @ 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
    @ 2008-11-11 17:02:42

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

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

  • 0
    @ 2008-11-11 16:27:09

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

  • 0
    @ 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

信息

ID
1470
难度
4
分类
动态规划 点击显示
标签
递交数
607
已通过
247
通过率
41%
被复制
2
上传者