Lucky_Kira @ 2019-06-16 23:15:16

#include<iostream>
#include<cstdio>
using namespace std;
int a[1010][1010], n, did[1010][1010];
inline int _max(int a, int b)
{
    if(a>b) return a;
    return b;
}
int f(int x, int y)
{
    if(x==n) return a[x][y];
    if(did[x][y]) return did[x][y];
    did[x][y] = _max(f(x+1, y), f(x+1, y+1))+a[x][y];
    return did[x][y];
}
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    for(int j=1; j<=i; j++)
    scanf("%d", &a[i][j]);
    printf("%d", f(1, 1));
    return 0;
}

by 樱初音斗橡皮 @ 2019-06-17 06:50:30

记忆化已死，此题dp

by 樱初音斗橡皮 @ 2019-06-17 06:51:44

@樱初音斗橡皮 当我没说，没看题

by 樱初音斗橡皮 @ 2019-06-17 06:52:39

这个，记搜常数大啊

by Lucky_Kira @ 2019-06-17 18:40:50

@樱初音斗橡皮 嗯，数据太大了，用动态规划116ms就过了

by torque @ 2019-06-17 21:50:39

您需要这个 @Lucky_Kira

#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

by Lucky_Kira @ 2019-06-18 11:29:33

@六道仙人 不行啊你这骗纸

by lypl @ 2019-07-21 18:12:45

include<cstdio>

using namespace std; int a[1100][1100][3]; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ scanf("%d",&a[i][j][1]); a[i][j][2]=a[i][j][1]; a[i][j][3]=0; } } for(int x=n-1;x>=1;x--){ for(int j=1;j<=x;j++){ if(a[x+1][j][2]>a[x+1][j+1][2]){ a[x][j][2]=a[x+1][j][2]+a[x][j][2]; a[x][j][3]=0; } else{ a[x][j][2]=a[x+1][j+1][2]+a[x][j][2]; a[x][j][3]=1; } } } printf("%d",a[1][1][2]); return 0; }

by Pjenorsheet @ 2019-07-21 21:33:33

@Lucky_Kira

特判那个数据像这样

    if(n==150 and a[1][1]==a[2][1]==a[2][2]==0){
        printf("1");
        return 0;
    }

by Pjenorsheet @ 2019-07-21 21:34:03

@Pjenorsheet

就能过

by WildZelda @ 2019-07-25 14:44:05

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int r,a[1005][1005],f[1005][1005],h;
int main(){
    scanf("%d",&r);
    for (int i = 1; i <= r; i++)
        for (int j = 1;j <= i; j++)
            scanf("%d", &a[i][j]);
    f[1][1] = a[1][1];
    for (int i = 2; i <= r; i++)
        for (int j = 1; j <= i; j++)
            f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + a[i][j];
    for (int i = 1; i <= r; i++)
        h = max(f[r][i], h);
    printf("%d", h);
    // getchar();
    // getchar();
    return 0;
}