メモ

自分に向けて書いたメモを取り扱っています.

AOJ 0089 The Shortest Path on A Rhombic Path

方針

再帰をしろという天からの声が聞こえた気がしたので,再帰を書いたのですがなぜか通らず.
ということでfor文に直して解きました.
dp[i][j] := i段目j個目まで選んだときの最大の値
半分より上の時と下の時で進む方向が変わるので注意です.

コード

int main()
{
    int dp[128][128];
    int ans = 0;
    string s;
    vector<vector<int> > data;

    memset(dp, 0, sizeof dp);

    while(cin >> s)
    {
        vector<int> v;
        replace(s.begin(), s.end(), ',', ' ');
        stringstream ss(s);

        while(ss >> s)
            v.push_back(atoi(s.c_str()));

        data.push_back(v);
    }

    int center = data.size() / 2;
    dp[0][0] = data[0][0];

    for(int i = 1; i < data.size(); i++)
        for(int j = 0; j < data[i].size(); j++)
            dp[i][j] = max(dp[i - 1][j], (i <= center ? dp[i - 1][j - 1] : dp[i - 1][j + 1])) + data[i][j];

    cout << dp[data.size() - 1][0] << endl;
}

なぜか通らない再帰のコード

なんででしょう

int dfs(int x, int y)
{
    if(y == data.size() || x < 0 || data[y].size() <= x)
        return 0;

    return max(dfs(x, y + 1), (center >= y ? dfs(x + 1, y + 1) : dfs(x - 1, y + 1))) + data[y][x];
}

int main()
{
    /* 省略 */
    cout << dfs(0, 0) << endl;
}