AOJ 0089 The Shortest Path on A Rhombic Path

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0089

概要

ひし形上に並べられた整数が与えられる。
一番上から左下か右下に移動していったとき、
通過した整数の和の最大値を出力せよ。

解法

動的計画法で解く。

コード

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <string>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)

vector<int> parse(string s, char c) {
    int pre = 0;
    vector<int> v;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == c) {
            v.push_back(atoi(s.substr(pre, i - pre).c_str()));
            pre = i + 1;
        }
    }
    v.push_back(atoi(s.substr(pre, s.length() - pre).c_str()));
    return v;
}

int main()
{
    int m[100][100], mx, sz;
    string s;
    REP(i, 100) REP(j, 100) m[i][j] = -1;
    for (sz = 0; getline(cin, s); sz++) {
        vector<int> v = parse(s, ',');
        REP(i, v.size()) m[sz][i] = v[i];
    }
    int dp[100][100] = { m[0][0] };
    for (int i = 1; i < sz; i++) {
        if (i >= sz / 2) {
            for (int j = 0; j < i + 1; j++) {
                dp[i][j] = m[i][j] + max(dp[i - 1][j], dp[i - 1][j + 1]);
            }
        }
        else {
            for (int j = 0; j < sz - i; j++) {
                dp[i][j] = m[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j]);
            }
        }
    }
    cout << dp[sz - 1][0] << endl;
    return 0;
}