SRM407 Div2 Medium

500

メモ化

view plainprint?

1. const int N = 50 + 1;  
2. bool g[N][N];  
3.   
4. lli memo[N];  
5.   
6. lli rec(int n)  
7. {  
8.   lli &ret = memo[n];  
9.   if (ret != -1) return ret;  
10.   
11.   lli sum = 0;  
12.   
13.   for (int i = 0; i < (int)N; ++i) {  
14.     if (g[n][i]) sum += rec(i);  
15.   }  
16.   
17.   return ret = max(1LL, sum);  
18. }  
19.   
20. class CorporationSalary {  
21. public:  
22.   long long totalSalary(vector <string> R)  
23.   {  
24.     const int size = R.size();  
25.   
26.     fill(&g[0][0], &g[N - 1][N], false);  
27.   
28.     for (int i = 0; i < (int)size; ++i) {  
29.       for (int j = 0; j < (int)size; ++j) {  
30.         g[i][j] = R[i][j] == 'Y';  
31.       }  
32.     }  
33.   
34.     fill(memo, memo + N, -1);  
35.   
36.     lli sum = 0;  
37.     for (int i = 0; i < (int)size; ++i) {  
38.       sum += rec(i);  
39.     }  
40.     return sum;  
41.   }  
42. };  

const int N = 50 + 1;
bool g[N][N];

lli memo[N];

lli rec(int n)
{
  lli &ret = memo[n];
  if (ret != -1) return ret;

  lli sum = 0;

  for (int i = 0; i < (int)N; ++i) {
    if (g[n][i]) sum += rec(i);
  }

  return ret = max(1LL, sum);
}

class CorporationSalary {
public:
  long long totalSalary(vector <string> R)
  {
    const int size = R.size();

    fill(&g[0][0], &g[N - 1][N], false);

    for (int i = 0; i < (int)size; ++i) {
      for (int j = 0; j < (int)size; ++j) {
        g[i][j] = R[i][j] == 'Y';
      }
    }

    fill(memo, memo + N, -1);

    lli sum = 0;
    for (int i = 0; i < (int)size; ++i) {
      sum += rec(i);
    }
    return sum;
  }
};