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