#include <iostream>#include <stdio.h>#include <string.h>#include <stack>#include <queue>#include <map>#include <set>#include <vector>#include <math.h>#include <bitset>#include <algorithm>#include <climits>using namespace std;#define LS 2*i#define RS 2*i+1#define UP(i,x,y) for(i=x;i<=y;i++)#define DOWN(i,x,y) for(i=x;i>=y;i–)#define MEM(a,x) memset(a,x,sizeof(a))#define W(a) while(a)#define gcd(a,b) __gcd(a,b)#define LL long long#define N 25#define MOD 19999997#define INF 0x3f3f3f3f#define EXP 1e-8char s[100];int cas = 1;inline int getit(char c){if(c=='I') return 1;if(c=='V') return 5;if(c=='X') return 10;if(c=='L') return 50;return 100;}struct node{void init(){MEM(hsh,-1);st = 0;}void set(int x){if(hsh[x]!=-1) return;hsh[x] = st;//记录路径st = x;//记录尾指针}int st;int hsh[5005];} dp[55][55];inline void solve(node& a,node& b,node& c)//枚举所有的情况，，这里使用地址符号的时间比不使用要优化很多，原因我也不是很清楚了{int i,j;for(i = a.st; i>0; i=a.hsh[i]){for(j = b.st; j>0; j=b.hsh[j]){if(i>=j)c.set(i+j);elsec.set(j-i);}}}vector<int> ans;int main(){int i,j,k,len;W(~scanf("%s",s)){if(s[0]=='0')break;printf("Case %d:",cas++);int n = strlen(s);UP(i,0,n-1){dp[i][1].init();dp[i][1].set(getit(s[i]));}UP(len,2,n){UP(i,0,n-len){dp[i][len].init();UP(k,1,len-1){solve(dp[i][k],dp[i+k][len-k],dp[i][len]);}}}ans.clear();for(i = dp[0][n].st; i!=0; i=dp[0][n].hsh[i])ans.push_back(i);sort(ans.begin(),ans.end());len = ans.size();UP(i,0,len-1)printf(" %d",ans[i]);printf("\n");}return 0;}
我想，这就是旅行的真义吧。
