比赛 20160415 评测结果 WWWWWEEEEE
题目名称 烤鸡翅 最终得分 0
用户昵称 Satoshi 运行时间 0.404 s
代码语言 C++ 内存使用 15.75 MiB
提交时间 2016-04-15 10:12:02
显示代码纯文本
  1. #include <fstream>
  2. #include <algorithm>
  3. #define N 2010
  4. #define M 10000
  5. using namespace std;
  6. typedef long long ll;
  7. ifstream in("wing.in");
  8. ofstream out("wing.out");
  9. int n;
  10. int A[N]={0};
  11. int B[N]={0};
  12. int D[N]={0};
  13. int f[N][N]={0};//fij表示已经决策到第i位,已经满足了j个人的残余鸡翅的数量最大值
  14. int INF=(1<<28);
  15. void read()
  16. {
  17. int i;
  18. in>>n;
  19. for(i=1;i<=n;i++)in>>A[i];
  20. for(i=1;i<=n;i++)in>>B[i];
  21. for(i=1;i<=n;i++)D[i]=A[i]-B[i];
  22. }
  23. void work()
  24. {
  25. int i,j,temp,ans;
  26. for(i=0;i<=n;i++)
  27. {
  28. for(j=0;j<=n;j++)
  29. {
  30. f[i][j]=-INF;
  31. }
  32. }
  33. f[0][0]=0;
  34. for(i=1;i<=n;i++)
  35. {
  36. for(j=1;j<=n;j++)
  37. {
  38. f[i][j]=f[i-1][j];
  39. temp=f[i-1][j-1]+D[i];
  40. f[i][j]=max(f[i][j],temp);
  41. }
  42. }
  43. for(i=1;i<=n;i++)if(f[n][i]>=0)ans=i;
  44. //如果残余鸡翅,那么可行
  45. out<<ans<<endl;
  46. }
  47.  
  48. int main()
  49. {
  50. read();
  51. work();
  52. return 0;
  53. }