#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;
}    

• 复杂度是n^2 的 (2845) sunmoonstar_love 2005-07-28 19:47:26
  • disagree (0) frkstyc 2005-07-28 20:20:23
    • fevering you (0) mj101 2005-07-28 20:54:03
• check写的不对，dp的状态也不对 (2845) sunmoonstar_love 2005-07-28 20:55:56
  • =乱搞 (0) frkstyc 2005-07-28 20:56:36
    • 没写过超过60行的能AC的程序，除了昨天那个国际象棋写了204line (0) bupt 2005-07-28 20:59:20