Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

哥随机了10000*n个组数据了,都木有问题,可你还是wawawa,我容易不...

Posted by sicojuy at 2011-04-09 22:45:39 on Problem 1732
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator