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

SRM407 Div1Easy CorporationSalary

解法
各々についてDFSして足し合わせる。メモ化すると良い。

typedef long long ll;
class CorporationSalary {
public:
  
  ll memo[55];
  ll dfs(vector<string> &R, int idx) {
    if(memo[idx]) return memo[idx];
    ll& ret = memo[idx];
    int cnt = 0;
    for(int i=0; i<R[idx].size(); i++) {
      if(R[idx][i] == 'Y') {
        cnt ++;
        ret += dfs(R, i);
      }
    }
    if(!cnt) return ret = 1;
    return ret;
  }
  
  long long totalSalary(vector <string> relations) {
    memset(memo, 0, sizeof memo);
    ll sum = 0;
    for(int i=0; i<relations.size(); i++) {
      sum += dfs(relations, i);
    }
    return sum;
  }
};