NOIP 2000 普及组4 单词接龙 解题报告

哈，这题拿到手时刚开始不知道怎么开始，后来找到了突破点，用f[i][j]记录第i个字符串和第j个字符串重复的字符数，就是说把第i个字符串和第j个字符串之间接起来重合的字符数目。
把这个处理好了就好下手了，不过这里我忽略了两点，导致提交了几次。第一点f[i][j]中的i,j可以重复！也就是说自己可以接在自己后面，再一个就是记录f[i][j]的时候要注意，从字符串的后面开始搜索，这两点弄了我半个小时到一个小时的时间，具体代码如下。

C语言:

#include <stdio.h>
#include <string.h>
int n;
char str[20][101];
int len[20];
int f[20][20];
int ans = 0;
char used[20];

void srch(int now, int length)
{
 int i;
 if(ans < length){
 ans = length; //是等于而不是加等 
 }
 used[now]++;
 for(i = 0; i < n; i++){
 if((used[i] < 2) && (f[now][i] > 0)){
 srch(i, length + len[i] - f[now][i]);
 }
 }
 used[now]--;
}

int check(int x, int y)
{
 char *a = str[x], *b = str[y];
 char *t = str[x] + len[x] - 1;
 while(t != a){
 if(*t == b[0]){ //要从后面往前面搜, 我是从前面往后面搜的.. 
 if(strncmp(t, str[y], len[x] - (t - a)) == 0){
 if(t != a){
 return (len[x] - (t - a));
 }
 }
 }
 t--;
 }

 return 0;
}

int main(void)
{
 int i, j;
 int ch;
 scanf(%d\\n, &n);
 for(i = 0; i < n; i++){
 scanf(%s\\n, str[i]);
 len[i] = strlen(str[i]);
 }

 for(i = 0; i < n; i++){
 for(j = 0; j < n; j++){ //我本来是i,j 相等就continue;了, 结果发现还是要 
 f[i][j] = check(i, j);
 }
 }

 ch = getchar();
 for(i = 0; i < n; i++){
 if(str[i][0] == ch){
 srch(i, len[i]);
 }
 }
 printf(%d\\n, ans);
 return 0;
}

自认为本程序效率不错，望高手指出可改进之处。