比赛 10.10.18noip模拟 评测结果 AAAATTTTTT
题目名称 罪犯问题B 最终得分 40
用户昵称 了反取字名我擦 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-10-18 20:04:59
显示代码纯文本
#include<fstream>
#include<algorithm>
#include<string>

using namespace std;
ifstream fi("criminalb.in");
ofstream fo("criminalb.out");

void sh();
void dfs(int k,int lie);
void dfs2(int k,int lie);
void px();
void px2();

int m,n,p,s[1001][3]={0},ans=0;
bool ok=0;

int main()
{
	fi>>n>>m>>p;
	for(int i=1;i<=n;i++)
		fi>>s[i][2];
	sh();
	px2();
	dfs2(1,0);
	ok=0;
	px();
	dfs(1,0);
	fi.close();
	fo.close();
	return 0;
}
void px()
{
	int temp[3];
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			if(s[i][2]<s[j][2])
			{
				temp[0]=s[i][0];temp[1]=s[i][1];temp[2]=s[i][2];
				s[i][0]=s[j][0];s[i][1]=s[j][1];s[i][2]=s[j][2];
				s[j][0]=temp[0];s[j][1]=temp[1];s[j][2]=temp[2];
			}
}
void px2()
{
	int temp[3];
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			if(s[i][2]>s[j][2])
			{
				temp[0]=s[i][0];temp[1]=s[i][1];temp[2]=s[i][2];
				s[i][0]=s[j][0];s[i][1]=s[j][1];s[i][2]=s[j][2];
				s[j][0]=temp[0];s[j][1]=temp[1];s[j][2]=temp[2];
			}
}

void sh()
{
	int temp;
	for(int i=0;i<m;i++)
	{
		fi>>temp;
		if(temp>0)
			s[temp][0]++;
		else
			s[-temp][1]++;
	}
}	
void dfs(int k,int lie)
{
	if(lie>p)return;
	if(k>n){fo<<ans;ok=1;return;}
	if(ok==0)
		dfs(k+1,lie+s[k][0]);
	if(ok==0)
	{
		ans+=s[k][2];
		dfs(k+1,lie+s[k][1]);
		ans-=s[k][2];
	}
}
void dfs2(int k,int lie)
{
	if(lie>p)return;
	if(k>n){fo<<ans<<endl;ok=1;return;}
	if(ok==0)
	{
		ans+=s[k][2];
		dfs2(k+1,lie+s[k][1]);
		ans-=s[k][2];
	}
	if(ok==0)
		dfs2(k+1,lie+s[k][0]);
}