记录编号	39142	评测结果	EEEEEEEEEE
题目名称	数字计算	最终得分	0
用户昵称	CC	是否通过	未通过
代码语言	C++	运行时间	0.712 s
提交时间	2012-07-05 14:32:37	内存使用	1.37 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#define min(a,b) ((a)<(b)?(a):(b))
const int INF = 1027423549;int big = 250;
struct num {
    int v;
    num *next;
    num (int v,num *next): v(v),next(next) {};
}*d[21][21],*c[21][21];
typedef long long ll;
int a[30],T,n;
int f[21][21][251],b[21][21][251];
bool done[21][21][251],ok[21][21][251];
ll get(int l,int r) {
    ll o = 0;
    for (int i = l;i <= r;i++) {
        o = o * 10 + a[i];
        if (o > T) {
            o = big;
            return o;
        }
    }
    return o;
}
int main() {
    freopen("puzzle.in","r",stdin);
    freopen("puzzle.out","w",stdout);
    char ch;
    n = 0;
    while ((ch = getchar()) != '\n') 
        a[++n] = ch - '0';
    scanf("%d\n", &T);
    while (T != -1) {
        memset(f,61,sizeof(f));
        memset(b,61,sizeof(b));
        memset(done,0,sizeof(done));
        memset(ok,0,sizeof(ok));
        memset(d,0,sizeof(d));
        memset(c,0,sizeof(c));
        for (int len = 1;len <= n;len++) 
            for (int i = 1;i <= n - len + 1;i++) {
                int j = i + len - 1,tmp = get(i,j);
                f[i][j][tmp] = 0;
                if (!done[i][j][tmp]) {
                    d[i][j] = new num(tmp,d[i][j]);
                    done[i][j][tmp] = 1;
                }
                for (int k = i;k <= j - 1;k++) 
                    for (num *p = d[i][k];p;p = p->next) 
                        for (num *q = d[k + 1][j];q;q = q->next) {
                            int u = p->v * q->v;
                            if ((p->v == big || q->v == big) && u) u = big;
                            if (u > T) u = big;
                            f[i][j][u] = min(f[i][j][u],f[i][k][p->v] + f[k + 1][j][q->v] + 1);
                            if (!done[i][j][u]) {
                                done[i][j][u] = 1;
                                d[i][j] = new num(u,d[i][j]);
                            }
                        }
            }
        for (int len = 1;len <= n;len++)
            for (int i = 1;i <= n - len + 1;i++) {
                int j = i + len - 1;
                for (num *p = d[i][j];p;p = p->next) {
                    b[i][j][p->v] = min(b[i][j][p->v],f[i][j][p->v]);
                    if (!ok[i][j][p->v]) {
                        ok[i][j][p->v] = 1;
                        c[i][j] = new num(p->v,c[i][j]);
                    }
                }
                for (int k = i;k <= j - 1;k++)
                    for (num *p = c[i][k];p;p = p->next)
                        for (num *q = c[k + 1][j];q;q = q->next) {
                            int u = p->v + q->v;
                            if ((p->v == big || q->v == big) && u) u = big;
                            if (u > T) u = big;
                            b[i][j][u] = min(b[i][j][u],b[i][k][p->v] + b[k + 1][j][q->v] + 1);
                            if (!done[i][j][u]) {
                                done[i][j][u] = 1;
                                c[i][j] = new num(u,c[i][j]);
                            }
                        }
            }
        int ans = b[1][n][T];
        if (ans == INF) ans = -1;
        printf("%d\n", ans);
        n = 0;
        while ((ch = getchar()) != '\n') 
            a[++n] = ch - '0';
        scanf("%d\n", &T);
    }
    return 0;
}