记录编号	253145	评测结果	AAAAAAAAAA
题目名称	罪犯问题B	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.631 s
提交时间	2016-04-21 19:47:10	内存使用	0.68 MiB

#include<cstdio>
#include<algorithm>
//#include"debug.h"
using namespace std;

int n,m,k,i,j,v[1010];
int hash[2010],dp[2][50010],ans;
bool a,b;
//dp[j]表示讨论前i个罪犯，共j个居民说谎的最值 
//hash[i]表示指正i是罪犯的居民数，hash[i+n]表示指正i不是罪犯的居民数 

int main()
{
	freopen("criminalb.in","r",stdin);
	freopen("criminalb.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for (i=1;i<=n;i++) scanf("%d",&v[i]);
	for (i=1;i<=m;i++){
		scanf("%d",&j);
		hash[(j>0?j:n-j)]++;
	}
	//求最大值 
	a=true;
	for (i=1;i<=n;i++){
		b=!a;
		for (j=0;j<=k;j++) dp[b][j]=-99999999;
		for (j=k;j>=0;j--){
			if (j+hash[i]<=k) dp[b][j+hash[i]]=max(dp[b][j+hash[i]],dp[a][j]);
			if (j+hash[i+n]<=k) dp[b][j+hash[i+n]]=max(dp[b][j+hash[i+n]],dp[a][j]+v[i]);
		}
		a=b;
	}
	ans=dp[a][0];
	for (i=1;i<=k;i++) ans=max(ans,dp[a][i]);
	printf("%d\n",ans);
	//求最小值
	a=true;
	for (i=0;i<=k;i++) dp[a][i]=0;
	for (i=1;i<=n;i++){
		b=!a;
		for (j=0;j<=k;j++) dp[b][j]=99999999;
		for (j=k;j>=0;j--){
			if (j+hash[i+n]<=k) dp[b][j+hash[i+n]]=min(dp[b][j+hash[i+n]],dp[a][j]+v[i]);
			if (j+hash[i]<=k) dp[b][j+hash[i]]=min(dp[b][j+hash[i]],dp[a][j]);
		}
		a=b;
	}
	ans=dp[a][0];
	for (i=1;i<=k;i++) ans=min(ans,dp[a][i]);
	printf("%d\n",ans);
	return 0;
}