### Andrew Stankevich’s Contest #9解题报告 » ZOJ2698

ZOJ2698.cpp

```// You must perform a transformation in such a way that as many words as possible are transformed to numbers
// If there are several way to perform the transformation in such a way, you must do it so that the first number is as great as possible. If there are still several ways, maximize the second number, and so on.

#include <map>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <utility>

using namespace std;

const char* str[] = {"one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
const int num[] = {1, 2, 3, 4, 5, 6, 7, 8, 9 , 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 40, 50, 60, 70, 80, 90};
map<string, int> mp;
map<int, string> pm;

const int MAXN = 1000000;
char buf[MAXN];
int wc[MAXN], dp[MAXN], pre[MAXN], val[MAXN];
string w[MAXN];

bool isalpha(const string& s) {
return s.length() > 0 && isalpha(s[0]);
}

bool isspace(const string& s) {
for (string::const_iterator i = s.begin(); i != s.end(); ++i) {
if (!isspace(*i)) {
return false;
}
}
return true;
}

string tolower(string s) {
for (string::iterator i = s.begin(); i != s.end(); ++i) {
*i = tolower(*i);
}
return s;
}

typedef const string* ptr;

ptr skip(ptr p) {
while (isspace(*p)) {
++p;
}
return p;
}

// gao5
int find(const string& s) {
return mp.count(s) == 0 ? -1 : mp[s];
}

// [yz]
pair<int, ptr> gao4(ptr p) {
//	fprintf(stderr, "[4] '%s'\n", p->c_str());
int val = find(tolower(*p));
// assert(isalpha(*p));
if (val < 20) {	// include (val == -1)
return make_pair(val, p + 1);
} else {
ptr q = skip(p + 1);
int t = find(tolower(*q));
if (t != -1 && t < 10) {
return make_pair(val + t, q + 1);
} else {
return make_pair(val, p + 1);
}
}
}

// [xyz]
pair<int, ptr> gao3(ptr p) {
//	fprintf(stderr, "[3] '%s'\n", p->c_str());
int val;
// assert(isalpha(*p));
val = find(tolower(*p));
if (val == -1) {
return make_pair(-1, p + 1);
} else if (val < 10) {
ptr q = skip(p + 1);
if (tolower(*q) == "hundred") {
ptr r = skip(q + 1);
if (tolower(*r) == "and") {
pair<int, ptr> pip = gao4(skip(r + 1));
if (pip.first == -1) {
return make_pair(val * 100, q + 1);
} else {
return make_pair(val * 100 + pip.first, pip.second);
}
} else {
return make_pair(val * 100, q + 1);
}
} else {
return make_pair(val, p + 1);
}
} else {
return gao4(p);
}
}

// [def] thousand [ghi]
pair<int, ptr> gao2(ptr p) {
//	fprintf(stderr, "[2] '%s'\n", p->c_str());
pair<int, ptr> pip = gao3(p);
if (pip.first == -1) {
return pip;
}
ptr q = skip(pip.second);
if (tolower(*q) == "thousand") {
pair<int, ptr> qiq = gao3(skip(q + 1));
if (qiq.first == -1) {
return make_pair(pip.first * 1000, q + 1);
} else {
return make_pair(pip.first * 1000 + qiq.first, qiq.second);
}
} else {
return pip;
}
}

// [abc] million [def] thousand [ghi]
pair<int, ptr> gao1(ptr p) {
//	fprintf(stderr, "[1] '%s'\n", p->c_str());
pair<int, ptr> pip = gao3(p);
if (pip.first == -1) {
return pip;
}
ptr q = skip(pip.second);
if (tolower(*q) == "million") {
pair<int, ptr> qiq = gao2(skip(q + 1));
if (qiq.first == -1) {
return make_pair(pip.first * 1000000, q + 1);
} else {
return make_pair(pip.first * 1000000 + qiq.first, qiq.second);
}
} else {
return gao2(p);
}
}

pair<int, ptr> gao(ptr p) {
//	fprintf(stderr, "[0] '%s'\n", p->c_str());
if (!isalpha(*p)) {
return make_pair(-1, p + 1);
} else if (tolower(*p) == "zero") {
return make_pair(0, p + 1);
} else {
return gao1(p);
}
}

int main() {
for (size_t i = 0; i < sizeof(num) / sizeof(int); ++i) {
mp[str[i]] = num[i];
pm[num[i]] = str[i];
}

while (fgets(buf, sizeof(buf), stdin) != NULL) {
int n = 0;
do {
for (int begin = 0; buf[begin] != '\0';) {
int end = begin + 1;
if (isalpha(buf[begin])) {
while (buf[end] != '\0' && isalpha(buf[end])) {
++end;
}
} else {
while (buf[end] != '\0' && !isalpha(buf[end])) {
++end;
}
}
w[n++] = string(buf + begin, buf + end);
if (n >= MAXN) { throw 1; }
begin = end;
}
} while (fgets(buf, sizeof(buf), stdin) != NULL && buf[0] != '\n');
w[n] = "0";

char ch = '0';
//string s = "0";
wc[0] = 0;
for (int i = 1; i <= n; ++i) {
wc[i] = wc[i - 1] + isalpha(w[i - 1]);
}
dp[n] = 0;
val[n] = -1;
pre[n] = -1;
for (int i = n - 1; i >= 0; --i) {
dp[i] = -1;
//printf("[%d] ", i);
for (int j = n, k = j; j > i; j = k - 1) {
swap(w[j][0], ch);
//swap(s, w[j]); -> MLE
//printf("%d,", j);
pair<int, ptr> pip = gao(w + i);
k = pip.second - w;
int d = pip.first == -1 ? 0 : wc[k] - wc[i];
int v = pip.first == -1 ? val[i + 1] : pip.first;
if (dp[i] < dp[k] + d || (dp[i] == dp[k] + d && val[i] < v)) {
dp[i] = dp[k] + d;
val[i] = v;
pre[i] = k;
}
swap(w[j][0], ch);
//swap(s, w[j]); -> MLE
}
//printf(":: %d, %d, %d\n", dp[i], val[i], pre[i]);
}

for (int i = 0; i != n; i = pre[i]) {
if (dp[i] == dp[pre[i]]) {
printf("%s", w[i].c_str());
} else {
printf("%d", val[i]);
}
}
puts("");
}
return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
//2178745 	2010-04-27 23:19:27 	Accepted 	2698 	C++ 	520 	20952 	watashi@Zodiac
```