比赛 |
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]);
}