Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

思路：先构造罗马与数字的映射，接着对给定的字符串从头开始进行最长匹配，最大为4，依次进行，匹配完成则乘以相应位的量级，时间复杂度为O(n)

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#define IMIN numeric_limits<int>::min()
#define IMAX numeric_limits<int>::max()
#define FR(i,n) for(int i=0;i<n;i++)
#define CLC(x) memset(x,0,sizeof(x))
#define FILL(x,c) memset(x,c,sizeof(x))
using namespace std;
class Solution {
public:
    int romanToInt(string s) {
        map<string,int> mp[4];
        init4(mp[3]);init3(mp[2]);init2(mp[1]);init1(mp[0]);
        int n=s.size();
        int res=0;
        for(int i=0;i<n;++i)
        {
            int len = min(n-i,4);
            int go_len = 0;
            while(len)
            {
                string tmp(s,i,len);
                int flag =0;
                for(int j=3;j>=0;--j)
                    if(mp[j].count(tmp)){
                        go_len = len;
                        res+=pow(10,j)*mp[j][tmp];
                        flag = 1; break;
                    }
                if(flag==1)break;
                len--;
            }
            i = i+go_len-1;
        }
        cout<<res<<endl;
        return res;
    }
    void init1(map<string,int> &mp)
    {
        mp[""]=0;
        mp[string("I")]=1;mp[string("II")]=2;
        mp[string("III")]=3;mp[string("IV")]=4;
        mp[string("V")]=5;mp[string("VI")]=6;
        mp[string("VII")]=7;mp[string("VIII")]=8;
        mp[string("IX")]=9;
    }
    void init2(map<string,int> &mp)
    {
        mp[""]=0;
        mp[string("X")]=1;mp[string("XX")]=2;
        mp[string("XXX")]=3;mp[string("XL")]=4;
        mp[string("L")]=5;mp[string("LX")]=6;
        mp[string("LXX")]=7;mp[string("LXXX")]=8;
        mp[string("XC")]=9;
    }
    void init3(map<string,int> &mp)
    {
        mp[""]=0;
        mp[string("C")]=1;mp[string("CC")]=2;
        mp[string("CCC")]=3;mp[string("CD")]=4;
        mp[string("D")]=5;mp[string("DC")]=6;
        mp[string("DCC")]=7;mp[string("DCCC")]=8;
        mp[string("CM")]=9;
    }
    void init4(map<string,int> &mp)
    {
        mp[string("M")]=1;mp[string("MM")]=2;
        mp[string("MMM")]=3;
    }
};
int main()
{
    Solution s;
    string str;
    while(cin>>str)
    cout<<s.romanToInt(str)<<endl;
    return 0;
}