记录编号	44334	评测结果	AAAAAAAAAA
题目名称	电话号码	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2012-10-18 10:35:13	内存使用	2.14 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200, M = 10000;
const char c[] = "adgkmorux\0";
int t['z'];
int n, l, a[N][N];
char p[N][N];
void print(int u, int v) {
    if(a[u][v] > M)
        printf("%s ", p[a[u][v] - M]);
    else {
        print(u, a[u][v]);
        print(a[u][v] + 1, v);
    }
}
bool ok(char s[], int u, int v) {
    for(int i=u; i<=v; i++)
        if(p[0][i-1] - '0' != t[s[i - u] - 'a'])
            return false;
    return true;
}
void chu(int u, int v) {
    //fprintf(stderr, "(%d,%d) ", u, v);
    for(int i=1; i<=n; i++)
        if(strlen(p[i]) == v - u + 1)
            if(ok(p[i], u, v)) { a[u][v] = i + M; return; }
    for(int i=u; i<v; i++) {
        if(a[u][i] == 0) chu(u, i);
        if(a[i+1][v] == 0) chu(i+1, v);
        if(a[u][i] < 0 || a[i+1][v] < 0)
            continue;
        else { a[u][v] = i; return; }
    } a[u][v] = -1;
}
int main() {
    freopen("denwa.in", "r", stdin);
    freopen("denwa.out", "w", stdout);
    for(int i=0; c[i]; i++)
        for(int j=c[i]; j<='z'; j++)
            t[j - 'a']++;
    for(int j='a'; j<='z'; j++)
        fprintf(stderr, "%d,", t[j - 'a']);
    scanf("%d\n", &n);
    scanf("%s\n", p[0]);
    for(int i=1; i<=n; i++)
        scanf("%s\n", p[i]);
    chu(1, l = strlen(p[0]));
    if(a[1][l] < 0)
        printf("No Solutions!\n");
    else
        print(1, l);
    return 0;
}