最近经常性地在关键时刻掉链子。古希腊先哲说，人不会两次跌进同一个坑——确实，我跌进了两个坑，摔的鼻青脸肿。先是在杭电邀请赛上看错范围，把辅助数组开小，幸好同伴火眼金睛；这道题犯的错误几乎一摸一样，一个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;}

评论