77分求助

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

funkynoob @ 2023-08-22 21:45:19

test8开始WA,代码感觉无问题捏


#include <bits/stdc++.h>
using namespace std;
const int N = 510000;
typedef struct NumTree
{
    int value;
    int left;
    int right;
} NumTree;
NumTree numtrees[N];
int loc[N];
int DFS(NumTree numtrees[], int idx, int value) // 深搜
{
    if (value == 0)
        return 0;
    if (loc[idx] != 0)
        return loc[idx];
    int leftn = value + DFS(numtrees, numtrees[idx].left, numtrees[numtrees[idx].left].value);
    int rightn = value + DFS(numtrees, numtrees[idx].right, numtrees[numtrees[idx].right].value);
    return loc[idx] = leftn > rightn ? leftn : rightn;
}

int main()
{
    int r;
    while (cin >> r)
    {
        string line;
        int idx = 0;
        getline(cin, line);
        memset(loc, 0, sizeof(loc));
        memset(numtrees, 0, sizeof(numtrees)); // 值全部置为0,防止树高度小于上一树时出错
        for (int i = 0; i < r; i++)            // 搭建整个树
        {
            getline(cin, line);
            istringstream iss(line);
            while (iss >> numtrees[idx].value)
            {
                numtrees[idx].left = idx + 1 + i;
                numtrees[idx].right = idx + 2 + i;
                idx++;
            }
        }
        cout << DFS(numtrees, 0, numtrees[0].value) << endl;
    }
}

by zyhe2013 @ 2023-08-22 22:08:16

#include<iostream>
#include<cstdio>
using namespace std;

int n,f[1001][1001],a[1001][1001];

int main() {
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>a[i][j];
        }
    }
    f[1][1]=a[1][1];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if(i==1&&j==1)continue;
            f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
        }
    }
    int maxn=0;
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,f[n][i]);
    }
    cout<<maxn;
    return 0;
}

求关


by zyhe2013 @ 2023-08-22 22:08:57

这题用内个递推,对递推


by zyhe2013 @ 2023-08-22 22:10:08

你懂了吗?(调了好久给个关吧)


by funkynoob @ 2023-08-27 15:28:49

@zyhe2023 哟西,感谢感谢


|