请问错哪了

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

金城武 @ 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好像没有提交啊


|