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; }