最近经常性地在关键时刻掉链子。古希腊先哲说，人不会两次跌进同一个坑——确实，我跌进了两个坑，摔的鼻青脸肿。先是在杭电邀请赛上看错范围，把辅助数组开小，幸好同伴火眼金睛；这道题犯的错误几乎一摸一样，一个a[601][101]的数组开成了a[101][601]。最可恨的是这样的错误假如没有意识到，一辈子都找不出来！ZOJ上wrong answer映的我发绿，莫名其妙，怎么也该打出一个RunTimeError吧……结果我的程序几乎被改成BusyCai同学的程序了……

    这类词典型的dp题目倒也差不多，a[i][k]代表了第k个词语在填入第i个位置时的可能总数。只要扫描上一个位置的所有M词语a[i- 1][j]，满足情况者加入a[i][k]即可。BusyCai的写法比较好，用每个位置a[i][k]去加到下一个位置a[i + 1][j]。a[i][k]可能为0，节省了很多时间。

#include <cstdio>
#include <string>

int N, L, M, len, a[110][610];
char str[610][11];

void init ()
{
 int i;
 for ( i = 0; i < M; i ++ )
 {
  scanf ( "%s", str[i] );
 }
 memset ( a, 0, sizeof ( a ) );
 len = strlen ( str[0] );
}

int check ( int a, int b )
{
 int i;
 for ( i = 1; i < len; i ++ )
 {
  if ( str[a][i] != str[b][i - 1] )
   return 0;
 }
 return 1;
}

void dp ()
{
 int i, k, j;
 for ( k = 0; k < M; k ++ )
 {
  a[len][k] = 1;
 }
 for ( i = len; i < L; i ++ )
 {
  for ( k = 0; k < M; k ++ )
  {
   if ( a[i][k] )
    for ( j = 0; j < M; j ++ )
    {
     if ( check ( k, j ) )
      a[i + 1][j] += a[i][k];
    }
  }
 }
 int sum = 0;
 for ( k = 0; k < M; k ++ )
 {
  sum += a[L][k];
 }
 printf ( "%d\n", sum );
}

int main ()
{
 //freopen ( "in.txt", "r", stdin );
 while ( scanf ( "%d%d%d", &N, &L, &M ) != EOF )
 {
  if ( N + L + M == 0 )
   break;
  init ();
  dp ();
  //pa ();
 }
 return 0;
}

评论