金城武 @ 2020-04-26 16:34:47
#include <iostream>
using namespace std;
int a[100][100], s = 0, b[100][100] = { 0 }, max = 0;
void dfs(int x, int y, int step,int n)
{
int i, k, tx=x, ty=y;
int next[2][2] = { {1,0},{1,1} };
if (x == n)
{
if (s > max)
max = s;
s = 0;
return;
}
for (k = 0; k <= 1; k++)
{
s += a[tx][ty];
tx = x + next[k][0];
ty = y + next[k][1];
//if (ty > tx || b[tx][ty]==1)
//continue;
if (ty > tx)
continue;
dfs(tx, ty, step + 1,n);
//b[tx][ty] = 0;
tx-= next[k][0];
ty-= next[k][1];
}
return;
}
int main()
{
int step, n, i, j;
cin >> n;
for (i = 0; i < n; i++)
for (j = 0; j <= i; j++)
cin >> a[i][j];
b[0][0] = 1;
dfs(0, 0, 1,n);
cout << max;
}
by xhQYm @ 2020-04-26 16:35:59
dfs可海星。。
by Warriors_Cat @ 2020-04-26 16:36:11
这道题正解是动态规划/记忆化搜索,普通剪枝过不了。
by xhQYm @ 2020-04-26 16:36:41
lz好像没有提交啊