巢穴

about:blank

usaco 4.3 lgame

/*
ID:ccl03261
LANG:C++
TASK:lgame
*/


#include 
<iostream>
#include 
<string>
#include 
<fstream>
#include 
<vector>
#include 
<algorithm>
using namespace std;
ifstream fin(
"lgame.in");
ifstream dfin(
"lgame.dict");
ofstream fout(
"lgame.out");
vector
<string> v;
string input_str;
string str[40001];
int n=0;
int hash[26],phash[26];
int t[40001][26];
int score[26]={2,5,4,4,1,6,5,5,1,7,6,3,5,2,3,5,7,2,1,2,4,6,6,7,5,7};
int main()
{
    
for (int i=0;i<26;i++)
     hash[i]
=0;
    fin
>>input_str;
    
for (int i=0;i<input_str.length();i++)
     hash[input_str[i]
-'a']++;
    
for (int i=0;i<40001;i++)
     
for (int j=0;j<26;j++)
      t[i][j]
=0;
    
while(1)
    
{
     
string s;
     dfin
>>s;
     
if (s=="."break;
     
for (int i=0;i<26;i++) phash[i]=0;
     
for (int i=0;i<s.length();i++)
      phash[s[i]
-'a']++;
     
bool ok=true;
     
for (int i=0;i<26;i++)
      
if (phash[i]>hash[i]) {ok=false;break;}
     
if (ok) {n++;str[n]=s;for (int i=0;i<26;i++){t[n][i]=phash[i];}}
    }

    
    
int max_=0;
    str[
0]="";
    
for (int i=0;i<=n;i++)
    
{
     
for (int j=i+1;j<=n;j++)
     
{
      
for (int l=0;l<26;l++) phash[l]=0;
      
for (int k=0;k<26;k++)
       phash[k]
=t[i][k]+t[j][k];
      
bool ok=true;
      
for (int k=0;k<26;k++)
      
{
       
if (phash[k]>hash[k]) {ok=false;break;}
      }

      
      
if (ok)
      
{
       
int sum=0;
       
for (int k=0;k<26;k++)
         sum
+=phash[k]*score[k];
       
if (max_<sum) 
       
{
        max_
=sum;
        v.clear();
        
if (i==0) v.push_back(str[j]);
        
else
            v.push_back(str[i]
+" "+str[j]);
       }

       
else if (max_==sum)
            

               
if (i==0) v.push_back(str[j]);
               
else
                   v.push_back(str[i]
+" "+str[j]);
            }

      }

     }

    }

    fout
<<max_<<endl;
    sort(v.begin(),v.end());
    
for (int i=0;i<v.size();i++)
     fout
<<v[i]<<endl;
   
// system("pause");
    return 0;
}

posted on 2009-11-06 12:12 Vincent 阅读(154) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理