77分求助
查看原帖
77分求助
926487
funkynoob楼主2023/8/22 21:45

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;
    }
}
2023/8/22 21:45
加载中...