| Status |
In/Out |
TIME Limit |
MEMORY Limit |
Submit Times |
Solved Users |
JUDGE TYPE |
 |
stdin/stdout |
3s |
8192K |
439 |
74 |
Standard |
Io and Ao are playing a word game. They say a word in the dictionary by turns. The word in the dictionary only contains lowercase letters. And the end character of the former said word should be the same as the start character of the current said word. They can start the game from any word in the dictionary. Any word shouldn't be said twice. Now, we define the complexity of the game that is the sum length of all words said in the game. Give you a dictionary, can you tell me the max complexity of this word game?
Input
The first line contains a single positive integer n(0 < n <=12). Next n lines are n words in the dictionary. The length of each word will not exceed 100.
Output
A single integer represents the complexity of the game.
Sample Input
3
joj
jlu
acm
6
cctv
redcode
lindong
we
love
programming
3
daoyuanlee
come
on
Sample Output
6
11
10
Problem Source: provided by loon
#include<iostream>
#include<cstdlib>
using namespace std;
struct S
{
string a;
char begin;
char end;
int length;
}s[13];
int visited[13];
int temp;
void search(int a,int num,int pre)
{
for(int i=0;i<num;i++ )
{
if(s[i].begin==s[pre].end&&visited[i]==0)
{
visited[i]=1;
search(a+s[i].length,num,i);
if(a+s[i].length>temp)temp=a+s[i].length;
visited[i]=0;
}
}
}
int main()
{
freopen("s.txt","r",stdin);
freopen("key.txt","w",stdout);
int num;
while(cin>>num)
{
int i;
temp=0;
for( i=0;i<num;i++)
{
cin>>s[i].a;
s[i].length=(s[i].a).size();
s[i].begin=(s[i].a)[0];
s[i].end=(s[i].a)[s[i].length-1];
if(s[i].length>temp)
temp=s[i].length;
}
for(i=0;i<num;i++)
{
memset(visited,0,sizeof(visited));
visited[i]=1;
search(s[i].length,num,i);
}
cout<<temp<<endl;
}
//system("PAUSE");
return 0;
}
以上代码超时。完全可以剪枝。
举个例子
abc
cbd
dbm
dbacmdp
我的程序一直搜啊搜，每次搜完都重新开始。比如在以a开头后，搜到c，下次再搜索时直接利用c的结果，这是深搜的特点决定的！！！
*************************
这种类似的有序搜索都可以用 * 备忘录方法*
**************************
#include<iostream>
#include<cstdlib>
using namespace std;
int num;
struct S
{
string a;
char begin;
char end;
int length;
}s[13];
int visited[13];
int temp;
int sum[13];
int search(int pre)//·µ»Ø´ÓpreµãÒÔºóµÄ×ܵÄÖµ
{
int j=s[pre].length,k=0;
for(int i=0;i<num;i++ )
{
if(s[i].begin==s[pre].end&&visited[i]==0&&i!=pre)//必须要有I！=pre
{
visited[i]=1;
k=search(i)+s[pre].length;
if(k>j)j=k;
}
else
{
if(s[i].begin==s[pre].end&&i!=pre)//必须要有i!=pre
return sum[i]+s[pre].length;//相当于备忘录，而且无需visited[i]=0;
}
}
sum[pre]=j;
return j;
}
int main()
{
freopen("s.txt","r",stdin);
freopen("key.txt","w",stdout);
while(cin>>num)
{
int i,j;
temp=0;
j=0;
for( i=0;i<num;i++)
{
cin>>s[i].a;
s[i].length=(s[i].a).size();
s[i].begin=(s[i].a)[0];
s[i].end=(s[i].a)[s[i].length-1];
if(s[i].length>temp)
temp=s[i].length;
}
for(i=0;i<num;i++)
{
memset(visited,0,sizeof(visited));
memset(sum,0,sizeof(sum));
visited[i]=1;
j=search(i);
if(j>temp)
temp=j;
}
cout<<temp<<endl;
}
//system("PAUSE");
return 0;
}
因为I！=pre又错了几下。
以后debug尽量自己用眼睛看，更省时间！！！！！！！！！
posted on 2009-07-05 12:33
luis 阅读(315)
评论(0) 编辑 收藏 引用 所属分类:
搜索 、
给我启发题