SRM437 Div2 Medium

500

メモ化する。
貪欲だと思って撃沈した。

view plainprint?

1. const int N = 11;  
2. map<string, string> memo[N];  
3.   
4. string rec(string s, int k)  
5. {  
6.   if (k == 0) return s;  
7.   if (memo[k].count(s)) return memo[k][s];  
8.   string mx = "0";  
9.   for (int i = 0; i < s.size(); ++i) {  
10.     for (int j = i + 1; j < s.size(); ++j) {  
11.       if (i == 0 && s[j] == '0') continue;  
12.       swap(s[i], s[j]);  
13.       mx = max(mx, rec(s, k - 1));  
14.       swap(s[i], s[j]);  
15.     }  
16.   }  
17.   return memo[k][s] = mx;  
18. }  
19.   
20. class TheSwap {  
21. public:  
22.   int findMax(int n, int k)  
23.   {  
24.     char buff[100];  
25.     sprintf(buff, "%d", n);  
26.     string s(buff);  
27.   
28.     bool valid = false;  
29.     for (int i = 0; i < s.size(); ++i) {  
30.       for (int j = i + 1; j < s.size(); ++j) {  
31.         int a = s[i] - '0';  
32.         int b = s[j] - '0';  
33.         if (a && b) valid = true;  
34.         if (a == b) valid = true;  
35.       }  
36.     }  
37.     if (!valid) return -1;  
38.   
39.     fill(memo, memo + N, map<string, string>());  
40.     return atoi(rec(s, k).c_str());  
41.   }  
42. };  

const int N = 11;
map<string, string> memo[N];

string rec(string s, int k)
{
  if (k == 0) return s;
  if (memo[k].count(s)) return memo[k][s];
  string mx = "0";
  for (int i = 0; i < s.size(); ++i) {
    for (int j = i + 1; j < s.size(); ++j) {
      if (i == 0 && s[j] == '0') continue;
      swap(s[i], s[j]);
      mx = max(mx, rec(s, k - 1));
      swap(s[i], s[j]);
    }
  }
  return memo[k][s] = mx;
}

class TheSwap {
public:
  int findMax(int n, int k)
  {
    char buff[100];
    sprintf(buff, "%d", n);
    string s(buff);

    bool valid = false;
    for (int i = 0; i < s.size(); ++i) {
      for (int j = i + 1; j < s.size(); ++j) {
        int a = s[i] - '0';
        int b = s[j] - '0';
        if (a && b) valid = true;
        if (a == b) valid = true;
      }
    }
    if (!valid) return -1;

    fill(memo, memo + N, map<string, string>());
    return atoi(rec(s, k).c_str());
  }
};