89分 倒数第二个点tle了

MingXBD @ 2017-08-11 19:03:52

#include <bits/stdc++.h>
using namespace std;
int num[1001][1002]={0},sr[1001][1002]={0},n;
int s(int x,int y)
{
    if(y==n) return num[x][y];
    if(sr[x][y]!=0)return sr[x][y];
    sr[x][y]=(s(x,y+1))>(s(x+1,y+1))?(num[x][y]+s(x,y+1)):(num[x][y]+s(x+1,y+1));
    return sr[x][y];
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=i;j++)
    scanf("%d",&num[j][i]);
    cout<<s(1,1);
    return 0;
}

by Ninaye @ 2017-08-12 20:54:18

简单dp啊

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1000+10;
int N,C;
int dp[maxn][maxn];
int main(){
    while(~scanf("%d",&N)){
        for(int i = 0; i < N; i++)
            for(int j = 0; j <= i; j++)
                scanf("%d",&dp[i][j]);
        for(int i = N-2; i >= 0; i--)
            for(int j = 0; j <= i; j++)
                dp[i][j] += max(dp[i+1][j],dp[i+1][j+1]);
        printf("%d\n",dp[0][0]);
    }
    return 0;
}

by Jeferay @ 2019-02-16 11:57:19

数据太多写不上来，大概就是一堆0里面倒数第n行有个1 把记忆花搜索的条件改为！=-1试试