记录编号	44434	评测结果	AAAAAAAAAA
题目名称	[顾研NOIP] 项链	最终得分	100
用户昵称	临轩听雨ゐ	是否通过	通过
代码语言	C++	运行时间	0.680 s
提交时间	2012-10-18 18:59:05	内存使用	3.43 MiB

#include <fstream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
using namespace std;
ifstream in("necklaced.in");
ofstream out("necklaced.out");
struct
{
    int pos;
    int num;
}cc[200];
int n;
int a[200][200]={0};
bool b[200]={0};
int sum[200]={0};
int tmp=0,ans=0;

bool p()
{
    for(int i=1;i<=26;i++)
        if(sum[i]%2!=0)
            return false;
    return true;
}

int dfs(int x)
{
    if(tmp>ans)
		if(p()==true)
			ans=tmp;
    if(x>=n)
        return 0;
    if(!b[x+1])
    {
        tmp++;
        for(int i=1;i<=a[x+1][0];i++)
            sum[a[x+1][i]]++;
        dfs(x+1);
        tmp--;
        for(int i=1;i<=a[x+1][0];i++)
            sum[a[x+1][i]]--;
    }
    dfs(x+1);
}

int main()
{
    in>>n;
    char s[27];
    for(int i=1;i<=n;i++)
    {
        in>>s;
        int j;
        for(j=0;j<strlen(s);j++)
        {
            a[i][j+1]=s[j]-'A'+1;
            cc[a[i][j+1]].num++;
            cc[a[i][j+1]].pos=i;
        }
        a[i][0]=j+1;
    }
    for(int i=1;i<=26;i++)
        if(cc[i].num==1)
            b[cc[i].pos]=true;
    dfs(0);
    out<<ans<<endl;
    return 0;
}