2013年8月22日

UVa 10029 - Edit Step Ladders

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

int main() {
  int ans = 0;
  map<string, int> dis[17];
  char temp[99];
  while (gets(temp)) {
    string s(temp);
    int len = s.length(), longest = 0;
    for (int i = 0; s[i]; i++) {
      for (char c = 'a'; c <= 'z'; c++) {
        string pre = s;
        pre[i] = c;
        if (s < pre) {
          break;
        }
        if (dis[len].count(pre)) {
          longest = max(longest, dis[len][pre]);
        }
      }
    }
    for (int i = 0; s[i]; i++) {
      string pre = s.substr(0, i) + s.substr(i + 1);
      if (dis[len - 1].count(pre) && s > pre) {
        longest = max(longest, dis[len - 1][pre]);
      }
    }
    if (len < 16) {
      for (int i = 0; s[i]; i++) {
        for (char c = 'a'; c <= 'z'; c++) {
          string pre = s.substr(0, i) + c + s.substr(i);
          if (s < pre) {
            break;
          }
          if (dis[len + 1].count(pre) && s > pre) {
            longest = max(longest, dis[len + 1][pre]);
          }
        }
      }
    }
    dis[len][s] = longest + 1;
    ans = max(ans, longest + 1);
  }
  printf("%d\n", ans);
  return 0;
}

沒有留言:

張貼留言