| 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 閱讀(325)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
給我啟發題