比赛 20160415 评测结果 WWWWWTWTTT
题目名称 烤鸡翅 最终得分 0
用户昵称 collor 运行时间 4.083 s
代码语言 C++ 内存使用 4.14 MiB
提交时间 2016-04-15 09:46:01
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long LL;
const int maxn=250500;
int n;
int a[maxn],b[maxn],fm[maxn],f[maxn];
int read()
{
	int x=0; char ch=getchar();
	while (ch<'0'||ch>'9')ch=getchar();
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x;
}
void init()
{
	//memset(a[]);
	n=read();
	for (int i=1;i<=n;i++)a[i]=read();
	for (int i=1;i<=n;i++)b[i]=read();
	for (int i=1;i<=n;i++)a[i]+=a[i-1];
}
void work()
{
	int ans=0;
	memset(fm,0,sizeof(fm));
	memset(f,10,sizeof(f));
	f[0]=0;
	for (int i=1;i<=n;i++){
		if (b[i]+f[ans]<a[i]){
			ans++; f[ans]=b[i]+f[ans-1];
		}
		for (int j=1;j<=ans;j++){
			if (b[i]+f[j-1]<f[j])
				f[j]=b[i]+f[j]-1;
		}
	}
	cout<<ans<<'\n';
}
int main()
{
	freopen("wing.in","r",stdin);
	freopen("wing.out","w",stdout);
	init();
	work();
	return 0;
}