> #include <iostream>
> #include <string>
> using namespace std;
> string book[2600];
> int i,j,n,favor[2600],f[2600],pre[2600],answer[2600],num,max1,tmp;
> void shell_sort(string* a, int n)
> {
>     int gap,i,j,tmp1;
>     string tmp;
>     for(gap = 1; (gap *= 3) < n; gap++)
>         ;
>     for(gap /= 3; gap > 0; gap = (gap+1)/3)
>         for(i = gap; i < n; i++)
>             for(j = i - gap; j >= 0; j -= gap)
>             {
>                 if(a[j+gap]<a[j])
>                 {
>                     tmp = a[j]; a[j] = a[j+gap]; a[j+gap]= tmp;
>                     tmp1 = favor[j]; favor[j] = favor[j+gap]; favor[j+gap] = tmp1;
>                 }
>                 else
>                     break;
>             }    
> }
> bool check(string a, string b) {
> 	int pa,pb,ac,bc;
> 	pa = pb = 0;
> 	while (pa < a.size() && pb < b.size()) {
> 		while (!(a[pa]>='a'&&a[pa]<='z' || a[pa]>='A'&&a[pa]<='Z') && pa < a.size()) pa++;
>         while (!(b[pb]>='a'&&b[pb]<='z' || b[pb]>='A'&&b[pb]<='Z') && pb < b.size()) pb++;
> 		if (pa == a.size() || pb == b.size()) break;
> 		if (a[pa]>='a'&&a[pa]<='z') ac = a[pa]-'a';
> 		else ac = a[pa]-'A';
> 		if (b[pb]>='a'&&b[pb]<='z') bc = b[pb]-'a';
> 		else bc = b[pb]-'A';
> 		if (ac == bc) return false;
> 		pa++; pb++;
> 		}
> 	return true;
> } 
> int main()
> {
>     while(cin>>n)
>     {
>         for(i=0; i<n; i++)
>         {
>             cin>>favor[i];
>             cin.get();
>             getline(cin,book[i]);
>          //   cout<<book[i]<<endl;
>            // cin.get();
>         }
>         shell_sort(book,n);
>   /*      for(i=0; i<n; i++)
>         {
>             cout<<favor[i]<<"    "<<book[i]<<endl;
>         }    */
>         pre[0] = -1;
>         f[0] = favor[0];    
>         for(i=1; i<n; i++)
>         {
>             f[i] = tmp = favor[i];
>             pre[i] = -1;
>             for(j=0; j<i; j++)
>             {
>                 if(check(book[j],book[i]))
>                 {
>                     if(f[i]+f[j]>tmp)
>                     {
>                         tmp = f[i]+f[j];
>                         pre[i] = j;
>                     }    
>                 }    
>             }
>             f[i] = tmp;
>                 
>         }
>         max1 = 0;
>         for(i=1; i<n; i++)
>         {
>             if(f[i]>f[max1])
>                 max1 = i;
>         }
>         answer[0] = max1; 
>         num = 1;
>         i = max1;
>         while(pre[i]!=-1)
>         {
>             i = pre[i];
>             answer[num++] =  i;
>         }
>         cout<<num<<endl<<f[max1]<<endl;
>         while(num--)
>         {
>             cout<<book[answer[num]]<<endl;
>         }                
>     }    
>     return 0;
> }    
> 

• disagree (0) frkstyc 2005-07-28 20:20:23
  • fevering you (0) mj101 2005-07-28 20:54:03