題目
給出一個羅馬算式（其實就是數(shù)字用羅馬字母表示的算式），問是否成立；如果字母代表的是0-9，有沒有可能存在一種方案使得自然算式成立
解法
第一問很簡單，我就不說什么了。不過處理的時候有簡單的地方，如果第i個羅馬數(shù)字>第i-1個羅馬數(shù)字，結(jié)果就加上num[i]-2*[numi-1]。
第二問讓我糾結(jié)好久。。fzu賽區(qū)一個題目和這個一樣，不過那個數(shù)據(jù)量小。這題數(shù)據(jù)量MS很大。如果沒有剪枝的程序跑了1.5秒。。雖然uva是過了，poj卻差很多。后來google，找到一個日本人寫的代碼，跑了79ms。。。。仔細研讀，發(fā)現(xiàn)我漏了一個重要的剪枝條件：a+b=c能夠成立當且僅當c的位數(shù)<=1+max(a、b的位數(shù)并且c的位數(shù)>=
max(a、b的位數(shù))，就+了這一個判斷在POJ上就過了。。。。其他的還有很大的常數(shù)優(yōu)化空間，不過我這種人很懶的- -
代碼
1 //============================================================================
2 // Name : pku1213.cpp
3 // Author : yzhw
4 // Version :
5 // Copyright : yzhw
6 // Description : Hello World in C++, Ansi-style
7 //============================================================================
8
9 #include <iostream>
10 # include <cstdio>
11 # include <cstring>
12 # include <algorithm>
13 using namespace std;
14 char str[128],d[3][20];
15 int charmap[255],digit[255];
16 bool flag;
17 int GetRomanNum(char *num)
18 {
19 int res=digit[*num];
20 for(int i=1;num[i]!='\0';i++)
21 if(digit[num[i]]>digit[num[i-1]])
22 res=res-2*digit[num[i-1]]+digit[num[i]];
23 else res+=digit[num[i]];
24 return res;
25 }
26 int GetNormalNum(char *num)
27 {
28 int res=0;
29 for(int i=0;num[i]!='\0';i++)
30 res=res*10+charmap[num[i]];
31 return res;
32 }
33 bool search(int num,int pos)
34 {
35 if(num==3)
36 {
37 if(GetNormalNum(d[0])+GetNormalNum(d[1])==GetNormalNum(d[2]))
38 {
39 if(!flag)
40 {
41 flag=true;
42 return false;
43 }
44 else
45 return true;
46 }
47 else return false;
48 }
49 else if(d[num][pos]=='\0')
50 return search(num+1,1);
51 else
52 {
53 if(charmap[d[num][pos]]!=-1)
54 return search(num,pos+1);
55 else
56 {
57 for(int i=0;i<10;i++)
58 {
59 charmap[d[num][pos]]=i;
60 if(search(num,pos+1)) return 1;
61 charmap[d[num][pos]]=-1;
62 }
63 return 0;
64 }
65 }
66 }
67 bool search(int num)
68 {
69 if(num==3)
70 {
71 if(search(0,1)) return true;
72 else return false;
73 }
74 else if(charmap[d[num][0]]!=-1) return search(num+1);
75 else
76 {
77 for(int i=1;i<10;i++)
78 {
79 charmap[d[num][0]]=i;
80 if(search(num+1)) return true;
81 charmap[d[num][0]]=-1;
82 }
83 return false;
84 }
85 }
86 int main() {
87 digit['I']=1;
88 digit['V']=5;
89 digit['X']=10;
90 digit['L']=50;
91 digit['C']=100;
92 digit['D']=500;
93 digit['M']=1000;
94 while(true)
95 {
96 scanf("%s",str);
97 if(str[0]=='#') break;
98 strcpy(d[0],strtok(str,"+"));
99 strcpy(d[1],strtok(NULL,"="));
100 strcpy(d[2],strtok(NULL," "));
101 //test Roman Number
102 if(GetRomanNum(d[0])+GetRomanNum(d[1])==GetRomanNum(d[2]))
103 printf("Correct ");
104 else
105 printf("Incorrect ");
106 //test Normal Number
107 flag=false;
108 memset(charmap,-1,sizeof(charmap));
109 if(strlen(d[2])>max(strlen(d[0]),strlen(d[1]))+1||strlen(d[2])<max(strlen(d[0]),strlen(d[1])))
110 {
111 printf("impossible\n");
112 continue;
113 }
114 if(search(0)) printf("ambiguous\n");
115 else if(flag) printf("valid\n");
116 else printf("impossible\n");
117 }
118 return 0;
119 }
120