巢穴

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   知识库   博问   管理