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