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 哟西,感谢感谢