SRM520 Div2 Hard

1000
メモ化する。直前の1行を覚えておけばいい。

view plainprint?

1. const int mod = 1000000007;  
2.   
3. const int N = 50 + 1;  
4. const int M = 3 + 1;  
5. map<string, lli> memo[N];  
6.   
7. bool cmp(string a, string b)  
8. {  
9.   int a_pass = count(a.begin(), a.end(), 'P');  
10.   int b_pass = count(b.begin(), b.end(), 'P');  
11.   if (a_pass > b_pass) return true;  
12.   
13.   int a_chal = count(a.begin(), a.end(), 'C');  
14.   int b_chal = count(b.begin(), b.end(), 'C');  
15.   if (a_pass == b_pass && a_chal <= b_chal) return true;  
16.   
17.   return false;  
18. }  
19.   
20. lli rec(int n, string prev, const vector<string> &D)  
21. {  
22.   if (n < 0) return 1;  
23.   if (memo[n].count(prev)) return memo[n][prev];  
24.   
25.   const int Y = count(D[n].begin(), D[n].end(), 'Y');  
26.   
27.   const string s = "PCFN";  
28.   string t = "@@@";  
29.   
30.   lli sum = 0;  
31.   
32.   for (int a = 0; a < s.size(); ++a) {  
33.     if (D[n][0] == 'N' || s[a] == 'N') if (D[n][0] != s[a]) continue;  
34.     for (int b = 0; b < s.size(); ++b) {  
35.       if (D[n][1] == 'N' || s[b] == 'N') if (D[n][1] != s[b]) continue;  
36.       for (int c = 0; c < s.size(); ++c) {  
37.         if (D[n][2] == 'N' || s[c] == 'N') if (D[n][2] != s[c]) continue;  
38.   
39.         t[0] = s[a];  
40.         t[1] = s[b];  
41.         t[2] = s[c];  
42.   
43.         int pass = count(t.begin(), t.end(), 'P');  
44.         int chal = count(t.begin(), t.end(), 'C');  
45.         int fail = count(t.begin(), t.end(), 'F');  
46.   
47.         if (pass + chal + fail == Y && cmp(t, prev) ) {  
48.           sum = (sum + rec(n - 1, t, D)) % mod;  
49.         }  
50.       }  
51.     }  
52.   }  
53.   return memo[n][prev] = sum;  
54. }  
55.   
56. class SRMSystemTestPhase {  
57. public:  
58.   int countWays(vector <string> D)  
59.   {  
60.     fill(memo, memo + N, map<string, lli>());  
61.     return rec((int)D.size() - 1, "CCC", D);  
62.   }  
63. };  

const int mod = 1000000007;

const int N = 50 + 1;
const int M = 3 + 1;
map<string, lli> memo[N];

bool cmp(string a, string b)
{
  int a_pass = count(a.begin(), a.end(), 'P');
  int b_pass = count(b.begin(), b.end(), 'P');
  if (a_pass > b_pass) return true;

  int a_chal = count(a.begin(), a.end(), 'C');
  int b_chal = count(b.begin(), b.end(), 'C');
  if (a_pass == b_pass && a_chal <= b_chal) return true;

  return false;
}

lli rec(int n, string prev, const vector<string> &D)
{
  if (n < 0) return 1;
  if (memo[n].count(prev)) return memo[n][prev];

  const int Y = count(D[n].begin(), D[n].end(), 'Y');

  const string s = "PCFN";
  string t = "@@@";

  lli sum = 0;

  for (int a = 0; a < s.size(); ++a) {
    if (D[n][0] == 'N' || s[a] == 'N') if (D[n][0] != s[a]) continue;
    for (int b = 0; b < s.size(); ++b) {
      if (D[n][1] == 'N' || s[b] == 'N') if (D[n][1] != s[b]) continue;
      for (int c = 0; c < s.size(); ++c) {
        if (D[n][2] == 'N' || s[c] == 'N') if (D[n][2] != s[c]) continue;

        t[0] = s[a];
        t[1] = s[b];
        t[2] = s[c];

        int pass = count(t.begin(), t.end(), 'P');
        int chal = count(t.begin(), t.end(), 'C');
        int fail = count(t.begin(), t.end(), 'F');

        if (pass + chal + fail == Y && cmp(t, prev) ) {
          sum = (sum + rec(n - 1, t, D)) % mod;
        }
      }
    }
  }
  return memo[n][prev] = sum;
}

class SRMSystemTestPhase {
public:
  int countWays(vector <string> D)
  {
    fill(memo, memo + N, map<string, lli>());
    return rec((int)D.size() - 1, "CCC", D);
  }
};