| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
哥随机了10000*n个组数据了,都木有问题,可你还是wawawa,我容易不...#include <cstring>
#include <cstdio>
using namespace std;
#define inf 10000
struct node
{
int ch[100];
int pos;
};
char word[50001][51];
char numw[50001][51];
int map[101][101];
int len[50001];
char num[101];
int n, lenn;
char r[26] = {'2', '2', '2', '3', '3', '3', '4', '4', '1', '1', '5', '5', '6', '6', '0', '7', '0', '7', '7', '8', '8', '8', '9', '9', '9', '0'};
struct node dp[101];
int main()
{
int i, j, k;
char *p;
while(scanf("%s", num) != EOF)
{
memset(map, 0, sizeof(map));
scanf("%d", &n);
lenn = strlen(num);
for(i = 1; i <= n; ++i)
{
scanf("%s", word[i]);
len[i] = strlen(word[i]);
for(j = 0; j < len[i]; ++j)
{
numw[i][j] = r[word[i][j] - 'a'];
}
numw[i][j] = '\0';
}
for(i = 1; i <= n; ++i)
{
k = 0;
while(1)
{
p = strstr(num + k, numw[i]);
if(p == NULL)
break;
k = p - num;
map[k][k + len[i]] = i;
k += len[i];
}
}
dp[0].pos = 0;
for(i = 1; i <= lenn; ++i)
dp[i].pos = inf;
for(i = 0; i < lenn; ++i)
for(j = 0; j <= lenn; ++j)
{
if(map[i][j] > 0)
{
if(dp[i].pos < dp[j].pos)
{
dp[j] = dp[i];
dp[j].ch[dp[j].pos] = map[i][j];
++dp[j].pos;
}
}
}
if(dp[lenn].pos == inf)
printf("No solution.\n");
else
{
printf("%s", word[dp[lenn].ch[0]]);
for(i = 1; i < dp[lenn].pos; ++i)
printf(" %s", word[dp[lenn].ch[i]]);
printf("\n");
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator