naoya_t@topcoder

SRM407 Div1 Easy: CorporationSalary

過去問, 練習 | 18:04 |

再帰的に計算。メモ化。

class CorporationSalary {
  int N;
  vector<long long> salary;
  vector<vector<bool> > t;

  long long decide_salary(int id){
    if (salary[id] > 0) return salary[id];
    long long s=0LL;
    rep(j,N){
      if(t[id][j]) s+=decide_salary(j);
    }
    if (s==0LL) s=1LL;
    return salary[id] = s;
  }
public:
  long long totalSalary(vector<string> relations) {
    N = relations.size(); //1-50

    t.resize(N); tr(t,it) it->resize(N);
    rep(i,N) rep(j,N) t[i][j]=(relations[i][j]=='Y');

    salary.resize(N); tr(salary,it) *it=0;

    long long total=0LL;
    rep(i,N) total+=decide_salary(i);
    return total;
  }
};