P1216,已经无了

P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles

Aresene @ 2021-12-14 16:50:28

求助,一个笨办法(>=10就必定TLE),写递归,但是就一个传值报错整疯了,人都不好了。

已经困扰了我

time_t *t = gettime();

#include <bits/stdc++.h>
using namespace std;
int js(int n,int x,int y,int a[][n]){
    if(y <= n){
        if(x <= y){
            int tmp = (a[x][y] + js(n,x,y+1,a)),tmp1 = a[x][y] + js(n,x+1,y+1,a);
            return tmp >= tmp1 ? tmp : tmp1;
        }else return 0;
    }else return 0;
}
int main(){
    int n;
    cin >> n;
   int a[n][n];
    for (int i = 1;i <= n;i++)for(int j = 1;j <= i;j++)cin >>a[i][j];
    cout << js(n,0,0,a) << endl;
    return 0;
}

by Dream_weavers @ 2021-12-14 17:02:32

dp是个好东西,你值得拥有

#include<bits/stdc++.h>
using namespace std;
long long i,j,n,a[1005][1005],f[1005][1005];
int main()
{
    cin>>n;
    for(i=1;i<=n;i++) for(j=1;j<=i;j++) cin>>a[i][j];
    for(i=n;i>0;i--)
    {
        for(j=1;j<=i;j++)
        {
            f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
        }
    }cout<<f[1][1];
    return 0;
}

|