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