比赛 顾研NOIP2011模拟赛 评测结果 AWAWAWWWWW
题目名称 项链 最终得分 30
用户昵称 临轩听雨ゐ 运行时间 0.627 s
代码语言 C++ 内存使用 3.43 MiB
提交时间 2012-10-17 21:01:46
显示代码纯文本
#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)
		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]=s[j]-'A'+1;
			cc[a[i][j]].num++;
			cc[a[i][j]].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;
}