话说这样子也算是记忆化搜索吧，为什么只有55分，其他都TLE了

exi3t @ 2020-01-11 00:15:56

#include<iostream>
#include<cstdio>
#define inf 0x7f7f7f7f
#define loop(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int a[1000+1][1000+1],f[1000+1][1000+1],n,ans;
int get(int,int);
int main()
{
    cin>>n;
    loop(i,1,n) loop(j,1,i) cin>>a[i][j];
    loop(i,1,n) ans=max(ans,get(n,i));
    cout<<ans<<endl;
    return 0;
}
int get(int x,int y)
{
    if(x<1 or y<1) return 0;
    if(f[x][y]) return f[x][y];
    return f[x][y]=max(get(x-1,y-1),get(x-1,y))+a[x][y];
}

by lndjy @ 2020-01-11 06:45:17

DP不香吗

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n+5][n+5];
    int dp[n+5][n+5];
    memset(a,0,sizeof a);
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=i;j++)
    cin>>a[i][j];
    for(int i=n;i>=1;i--)
    for(int j=1;j<=i;j++)
    {
        dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
    }
    cout<<dp[1][1];
    return 0;
}

by 焚魂 @ 2020-01-22 17:35:27

DP不香吗

by JRzyh @ 2020-02-01 10:29:39

DP不香吗

by 19ty53 @ 2020-02-07 12:50:09

可以用动态规划

#include <cstdio>
#include <iostream>
#include <cctype>
#include <queue>
#define C c = tc ( )
using namespace std;
int n,a[1001][1001],f[1001][1001],maxn;
inline char tc(){
    static char fl[100000],*A,*B;
    return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}

inline void fread(int &x){
    static char c;
    while(!isdigit(C));x=c-'0';
    while(isdigit(C))x=(x<<3)+(x<<1)+(c^48);
}
int main(){
    fread(n);
    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=i;++j){
            fread(a[i][j]);
        }
    }
    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=i;++j){
            f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
            maxn=max(f[i][j],maxn);
        }
    }
    printf("%d",maxn);
}

by djwj233 @ 2020-02-10 13:11:17

DP它不香吗

by stdout @ 2020-03-18 21:55:38

DP它不香吗