読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0089

菱形上の最短経路 | Aizu Online Judge
添字の扱いが厄介

vector<string> split(const string &str, char delim)
{
  istringstream iss(str); string tmp; vector<string> res;
  while(getline(iss, tmp, delim)) res.push_back(tmp);
  return res;
}


int main()
{
  vector<int> v;
  string s;
  while(cin >> s)
  {
    auto u = split(s,',');
    for(auto a : u) v.push_back(atoi(a.c_str()));
  }
  int n = sqrt(v.size());
  vector<vector<int> > T(n,vector<int>(n,0));
  int c = 0;
  REP(i,2*n-1) REP(j,((i<n)?i+1:2*n-1-i))
  {
    if(i<n) T[i-j][j] = v[c++];
    else T[n-j-1][i-n+1+j] = v[c++];
  }
  FOR(i,1,n-1) { T[0][i] += T[0][i-1]; T[i][0] += T[i-1][0];}
  FOR(i,1,n-1) FOR(j,1,n-1) T[i][j] += max(T[i-1][j],T[i][j-1]);
  cout << T[n-1][n-1] << endl;
}