SRM411 Div2 Medium

600

memo[ どこまで作った ] = 最小コスト

view plainprint?

1. const int N = 50 + 1;  
2. int memo[N];  
3.   
4. string S;  
5. vector<string> W;  
6.   
7. const int inf = 1 << 29;  
8.   
9. int cost(string a, string b)  
10. {  
11.   if (a.size() != b.size()) return inf;  
12.   string sa = a;  
13.   string sb = b;  
14.   sort(sa.begin(), sa.end());  
15.   sort(sb.begin(), sb.end());  
16.   
17.   if (sa != sb) return inf;  
18.   
19.   int diff = 0;  
20.   for (int i = 0; i < b.size(); ++i) {  
21.     diff += a[i] != b[i];  
22.   }  
23.   return diff;  
24. }  
25.   
26. int rec(int n)  
27. {  
28.   if (n == S.size()) return 0;  
29.   int &ret = memo[n];  
30.   if (ret != -1) return ret;  
31.   
32.   int mn = inf;  
33.   
34.   string s;  
35.   for (int i = 0; n + i < S.size(); ++i) {  
36.     s += S[n + i];  
37.     for (int j = 0; j < W.size(); ++j) {  
38.       int m = cost(s, W[j]);  
39.       if (m != inf) {  
40.         mn = min(mn, rec(n + i + 1) + m);  
41.       }  
42.     }  
43.   }  
44.   
45.   return ret = mn;  
46. }  
47.   
48. class SentenceDecomposition {  
49. public:  
50.   int decompose(string sentence, vector <string> validWords)  
51.   {  
52.     S = sentence;  
53.     W = validWords;  
54.   
55.     fill(memo, memo + N, -1);  
56.     int ret = rec(0);  
57.     return ret == inf ? -1 : ret;  
58.   }  
59. };  

const int N = 50 + 1;
int memo[N];

string S;
vector<string> W;

const int inf = 1 << 29;

int cost(string a, string b)
{
  if (a.size() != b.size()) return inf;
  string sa = a;
  string sb = b;
  sort(sa.begin(), sa.end());
  sort(sb.begin(), sb.end());

  if (sa != sb) return inf;

  int diff = 0;
  for (int i = 0; i < b.size(); ++i) {
    diff += a[i] != b[i];
  }
  return diff;
}

int rec(int n)
{
  if (n == S.size()) return 0;
  int &ret = memo[n];
  if (ret != -1) return ret;

  int mn = inf;

  string s;
  for (int i = 0; n + i < S.size(); ++i) {
    s += S[n + i];
    for (int j = 0; j < W.size(); ++j) {
      int m = cost(s, W[j]);
      if (m != inf) {
        mn = min(mn, rec(n + i + 1) + m);
      }
    }
  }

  return ret = mn;
}

class SentenceDecomposition {
public:
  int decompose(string sentence, vector <string> validWords)
  {
    S = sentence;
    W = validWords;

    fill(memo, memo + N, -1);
    int ret = rec(0);
    return ret == inf ? -1 : ret;
  }
};