比赛 20160415 评测结果 WWWWWEEEEE
题目名称 烤鸡翅 最终得分 0
用户昵称 Satoshi 运行时间 0.404 s
代码语言 C++ 内存使用 15.75 MiB
提交时间 2016-04-15 10:12:02
显示代码纯文本
#include <fstream>
#include <algorithm>
#define N 2010
#define M 10000
using namespace std;
typedef long long ll;
ifstream in("wing.in");
ofstream out("wing.out");
int n;
int A[N]={0};
int B[N]={0};
int D[N]={0};
int f[N][N]={0};//fij表示已经决策到第i位,已经满足了j个人的残余鸡翅的数量最大值
int INF=(1<<28);
void read()
{
	int i;
	in>>n;
	for(i=1;i<=n;i++)in>>A[i];
	for(i=1;i<=n;i++)in>>B[i];
	for(i=1;i<=n;i++)D[i]=A[i]-B[i];
}
void work()
{
	int i,j,temp,ans;
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			f[i][j]=-INF;
		}
	}
	f[0][0]=0;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			f[i][j]=f[i-1][j];
			temp=f[i-1][j-1]+D[i];
			f[i][j]=max(f[i][j],temp);
		}
	}
	for(i=1;i<=n;i++)if(f[n][i]>=0)ans=i;
	//如果残余鸡翅,那么可行
	out<<ans<<endl;
}

int main()
{
	read();
	work();
	return 0;
}