Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Huge input,scanf is recommended.

Posted by semonteer at 2005-09-24 20:25:06 on Problem 1171
In Reply To:帮我看看啊,为什么超时 Posted by:specious at 2005-09-24 20:05:02
> #include<iostream>
> #include<string>
> using namespace std;
> int val(string t)//计算分数
> {
> 	int count=0;
> 	for(int i=0;i<t.length ();i++)
> 	{
> 		switch(t.at(i))
> 		{
> 			case'a':count+=2;break;
> 			case'b':count+=5;break;
> 			case'c':count+=4;break;
> 			case'd':count+=4;break;
> 			case'e':count+=1;break;
> 			case'f':count+=6;break;
> 			case'g':count+=5;break;
> 			case'h':count+=5;break;
> 			case'i':count+=1;break;
> 			case'j':count+=7;break;
> 			case'k':count+=6;break;
> 			case'l':count+=3;break;
> 			case'm':count+=5;break;
> 			case'n':count+=2;break;
> 			case'o':count+=3;break;
> 			case'p':count+=5;break;
> 			case'q':count+=7;break;
> 			case'r':count+=2;break;
> 			case's':count+=1;break;
> 			case't':count+=2;break;
> 			case'u':count+=4;break;
> 			case'v':count+=6;break;
> 			case'w':count+=6;break;
> 			case'x':count+=7;break;
> 			case'y':count+=5;break;
> 			case'z':count+=7;break;
> 		}
> 	}
> 	return count;
> }
> 
> bool isright(int *num,string b)//判断是否有多余字母
> {
> 	int co[26]={0};
> 	for(int i=0;i<b.length();i++)
> 	{
> 		int n=b.at(i)-97;
> 		co[n]++;
> 		if(co[n]>num[n])
> 			return false;
> 	}
> 	return true;
> }
> 	
> 
> 
> int main()
> {
> 	string a[40000];//保存字符串
> 	string x;//保存原字符串
> 	cin>>x;
> 	int num[26]={0};
> 	int value[40000];//保存每个字符串的分数
> 	int len[40000];
> 	int mm=val(x);//保存原字符串的分数
> 	for(int i=0;i<x.length();i++)
> 	{
> 		num[int(x.at(i))-97]++;
> 	}
> 	int z=0;
> 	int max=0;
> 	for(i=0;i<40000;i++)
> 	{
> 		cin>>a[i];
> 		if(a[i].at(0)=='.') break;
> 		if(z==-1)continue;
> 		len[i]=a[i].length ();
> 		if(len[i]>7) continue;
> 		if(z==0&&isright(num,a[i])) 
> 		{
> 			value[i]=val(a[i]);
> 			if(value[i]==mm)
> 			{
> 				z=-1;
> 			}
> 		}
> 	}
> //	if(z==-1)
> //	{
> //		cout<<mm<<endl;
> //		return 0;
> //	}
> 
> 	for(int j=0;j<i;j++)
> 	{
> 		if(value[i]<0) continue;
> 		if(value[j]>max)
> 			max=value[j];
> 		if(len[j]==7) continue;
> 		for(int k=j+1;k<i;k++)
> 		{
> 			if(len[k]==7) continue;
> 			if(len[j]+len[k]>7) continue;
> 			string y=a[j]+a[k];
> 			if(isright(num,y)&&value[j]+value[k]>max) max=val(y);
> 			if(max==mm)
> 			{
> 				cout<<mm<<endl;
> 				return 0;
> 			}
> 		}
> 	}
> 			
> 	cout<<max<<endl;
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator