/*
0.062 1485 KB
*/
#include
<
iostream
>
using
namespace
std;
int
N;
const
char
*
d
=
"
22233344115566070778889990
"
;
char
a[
110
];
char
s[
50001
][
55
];
int
ans[
110
];
int
f[
110
];
bool
check(
int
x,
int
y){
int
len
=
strlen(s[y]);
for
(
int
i
=
0
;i
<
len;
++
i)
if
(a[x
-
i]
!=
d[s[y][len
-
i
-
1
]
-
'
a
'
])
return
0
;
return
1
;
}
void
out
(
int
len){
if
(
!
len)
return
;
out
(len
-
strlen(s[f[len]]));
if
(len
==
strlen(a))
printf(
"
%s\n
"
,s[f[len]]);
else
printf(
"
%s
"
,s[f[len]]);
}
int
main()
{
while
(
1
){
gets(a);
if
(strcmp(a,
"
-1
"
)
==
0
)
break
;
scanf(
"
%d
"
,
&
N); getchar();
for
(
int
i
=
0
;i
<
N;
++
i)
gets(s[i]);
memset(ans,
0x7F
,
sizeof
(ans));
memset(f,
-
1
,
sizeof
(f));
ans[
0
]
=
0
;
f[
0
]
=
0
;
for
(
int
i
=
0
;i
<
strlen(a);
++
i)
for
(
int
j
=
0
;j
<
N;
++
j)
if
(i
+
1
>=
strlen(s[j])
&&
a[i]
==
d[s[j][strlen(s[j])
-
1
]
-
'
a
'
])
if
(ans[i
+
1
]
>
ans[i
+
1
-
strlen(s[j])]
&&
check(i,j)){
ans[i
+
1
]
=
ans[i
+
1
-
strlen(s[j])]
+
1
;
f[i
+
1
]
=
j;
}
if
(f[strlen(a)]
==-
1
) printf(
"
No solution.\n
"
);
else
out
(strlen(a));
}
return
0
;
}
解法二：
/*
0.046
*/
#include<iostream>
using namespace std;
int N;
const char *d="22233344115566070778889990";
char map[110][110][256];
char sol[110][256];
char s[256];
int f[110];
void check(int x,char *y){
for(int i=0;i<strlen(y);++i)
if(s[x-i-1]!=d[y[strlen(y)-i-1]-'a'])
return;
strcpy(map[x][strlen(y)],y);
}
int main()
{
gets(s);
scanf("%d",&N); getchar();
for(int i=0;i<=strlen(s);++i){
sol[i][0]=0;
for(int j=0;j<=strlen(s);++j)
map[i][j][0]=0;
}
char ch[255];
for(int i=1;i<=N;++i){
gets(ch);
for(int j=strlen(ch);j<=strlen(s);++j)
check(j,ch);
}
f[0]=0;
for(int i=1;i<=strlen(s);++i){
if(strlen(map[i][i])==0){
f[i]=256;
strcpy(ch,sol[i]);
for(int j=1;j<i;++j)
if(f[i]>f[j]+1&&strlen(map[i][i-j])>0){
f[i]=f[j]+1;
strcpy(ch,sol[i]);
strcat(ch,sol[j]);
strcat(ch," ");
strcat(ch,map[i][i-j]);
}
strcpy(sol[i],ch);
}
else{
f[i]=1;
strcpy(sol[i],map[i][i]);
}
}
if(strlen(sol[strlen(s)])>0)
printf("%s\n",sol[strlen(s)]);
else
printf("No solution.\n");
return 0;
}
posted on 2009-05-25 15:43
xfstart07 阅读(305)
评论(0) 编辑 收藏 引用 所属分类:
代码库