USACO OPEN11 Forgotten Password

Problem 8: Forgotten Password [Damon Doucet, 2011]

As has happened to so many of us, Bessie has forgotten her cowtube
password. She does, however, remember some handy bits of information
about it.

First, she remembers that her password (denoted as variable P) has
length L (1 <= L <= 1,000) roman characters and can be split into
one or more words (not necessarily unique) from a dictionary composed
of NW (1 <= NW <= 1,000) unique words.  A word W_i is defined as a
sequence of 1..20 lowercase letters of the Roman alphabet ('a'..'z').

She also remembers certain letters from her password along with
their positions.

Consider the following example. Bessie knows that her password looks
like "a??l?ban???????" ('?' represents a letter she cannot remember),
and her dictionary has the following words:

apple
cow
farmer
banana
bananas
pies

The two possible passwords for Bessie to have are "applebananapies" and 
"applebananascow".

Given the dictionary, and the letters that Bessie remembers, please
find her password. If more than one password is valid, find the
lexicographically least string that works.

PROBLEM NAME: forgot

INPUT FORMAT:

* Line 1: Two space-separated integers: L and NW

* Line 2: A string of length L: P

* Lines 3..NW+2: Line i+2 contains the ith word in the dictionary: W_i

SAMPLE INPUT (file forgot.in):

15 6
a??l?ban???????
apple
cow
farmer
banana
bananas
pies

OUTPUT FORMAT:

* Line 1: The lexicographically least password that fits

SAMPLE OUTPUT (file forgot.out):

applebananapies

**********************************************************************

这题有明显的无后效性很明显，使用动态规划解决。类似完全背包，用can[i]记录长度为i的串能否实现，

不断扩展，复杂度为（L*NW*20） 

只是题目要求输出排序后最小的那个，根据最优子结构性质，只要加上一个char str[i][MAXLEN]，记录

长度为i时排序最靠前的那个串即可。

C语言: 高亮代码由发芽网提供

#include
#include
#include

int L,N;
char pass[1005];
char word[1005][25];
int len[1005];
int can[1005];
char str[1005][1005];
char tmp[1005];

void init()
{
   scanf("%d%d\n",&L,&N);
   scanf("%s\n",pass);
   int i;
   for(i = 0;i < N;i ++)
   {
       scanf("%s\n",word[i]);
       len[i] = strlen(word[i]);
   }
}

int match(char *a,char *b)
{
   for(;*a && *b;a ++,b ++)
   {
       if(*b == '?')    continue;
       if(*a != *b)    return 0;
   }
   return 1;
}

void dp()
{
   int i,j;
   can[0] = 1;
   for(i = 0;i <= L;i ++)
       if(can[i])
           for(j = 0;j < N;j ++)
               if(i + len[j] <= L && match(word[j],pass + i))
               {
                   if(can[i + len[j]] == 0)
                   {
                       can[i + len[j]] = 1;
                       memcpy(str[i + len[j]],str[i],i * sizeof(char));
                       memcpy(str[i + len[j]] + i,word[j],len[j] * sizeof(char));
                   }
                   else
                   {
                       strcpy(tmp,str[i]);
                       strcpy(tmp + i,word[j]);
                       if(strcmp(tmp,str[i + len[j]]) < 0)
                           memcpy(str[i + len[j]],tmp,1001 * sizeof(char));
                   }
               }
   puts(str[L]);
}

int main()
{
   freopen("forgot.in","r",stdin);
   freopen("forgot.out","w",stdout);
   init();
   dp();
   return 0;
}

起初本人程序中用得都是strcpy和strcat,在USACO上测试时超时了，换成memcpy就通过了。可见memcpy的效率大大高于strcpy。