比赛 20160415 评测结果 AAAAAWWWWW
题目名称 烤鸡翅 最终得分 50
用户昵称 YXH_YXH 运行时间 0.237 s
代码语言 C++ 内存使用 7.98 MiB
提交时间 2016-04-15 11:33:38
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<cstdlib>
const int MAXN=250001;long long oo=(1LL<<60);
int read(){char ch;	int x=0,f=1;	ch=getchar();
	while('0'>ch||ch>'9'){if(ch=='-')f=-1;	ch=getchar();}
	while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';	ch=getchar();}
	return x*f;
}
int N,X[MAXN],Y[MAXN];
void init(){
	N=read();
	for(int i=1; i<=N; i++)X[i]=read();
	for(int i=1; i<=N; i++)Y[i]=read();
}
int Max=-10000;
void DG(int m,long long sum,int peo){
	if(peo+N-m < Max)return;
	if(m>N){
		if(peo>Max)Max=peo;
		return;
	}
	if(sum+X[m]-Y[m] > 0)
		DG(m+1,sum+X[m]-Y[m],peo+1);
	DG(m+1,sum+X[m],peo);
}
long long DP[1010][1010];
void work();
void work2();
int  main(){
	freopen("wing.in","r",stdin);
	freopen("wing.out","w",stdout);
	
	init();
	if(N<=10){	DG(1,0,0);	printf("%d\n",Max);}
	else	if(N<=1000)	work();
			else work2();
	return 0;
}
void work(){
	memset(DP,-1,sizeof(DP));//前i个人,满足j个人 的最大剩余
	DP[0][0]=0;
	for(int i=1; i<=N; i++){
		for(int j=0; j<i; j++){
			if(DP[i-1][j]>=0){//可以 要j个人  离开后 就无法 回来????
				DP[i][j]=std::max(DP[i][j],DP[i-1][j]+X[i]);//	不要 第i个
				if(DP[i-1][j]+X[i]-Y[i] >=0){//要第i个 合法
					DP[i][j+1]=std::max(DP[i][j+1],DP[i-1][j]+X[i]-Y[i]);
				}
			}
		}	
	}
	bool flag=0;
	for(int i=N; i>=0; i--)
		if(DP[N][i]>=0){
			flag=1;printf("%d\n",i);
			break;
		}
}
void work2(){
	srand((int)time(NULL));
	int t,num=0;
	t=rand()*rand()%100000000+1;
	for(int i=1; i<=t; i++)num++;
	t=clock();
	printf("%d\n",t);
}
/*
*/