#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; }
Hello, I am a CS student from Taiwan.
I am learing English and Programming.
I'll save source code of some problems or small programs without comments in this blog.
I would recommend you not to read solution from others before you solved the problem.
(這邊專門存放沒有任何註解的小程式/OJ題目程式碼)
2013年8月22日
UVa 10029 - Edit Step Ladders
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言