CSU1622: Generalized Roman Numerals(区间DP)

#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-8

char 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);
            else
                c.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;
}