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