比赛 20160415 评测结果 WWWWWTWTTT
题目名称 烤鸡翅 最终得分 0
用户昵称 sro dydxh orz 运行时间 4.825 s
代码语言 C++ 内存使用 0.79 MiB
提交时间 2016-04-15 11:45:34
显示代码纯文本
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<algorithm>
  5. #include<cmath>
  6. #include<cstring>
  7. using namespace std;
  8. const int maxn=25000;
  9. int n,a[maxn+10],b[maxn+10],num[maxn+10][2],t[maxn];
  10. int f[maxn+10][2];//sell or not
  11. int main(){
  12. freopen("wing.in","r",stdin);
  13. freopen("wing.out","w",stdout);
  14. scanf("%d",&n);
  15. for(int i=1;i<=n;i++){
  16. scanf("%d",&a[i]);
  17. t[i]=t[i-1]+a[i];
  18. }
  19. for(int i=1;i<=n;i++) scanf("%d",&b[i]);
  20. for(int i=1;i<=n;i++){
  21. int tempp=0;bool flag=1;
  22. for(int k=1;k<i;k++){
  23. if(num[k][1]+t[i]-t[k]>=b[i])
  24. if(f[k][1]>f[i][0]){
  25. f[i][0]=f[k][1];tempp=k;flag=0;
  26. }
  27. if(num[k][0]+t[i]-t[k]>=b[i])
  28. if(f[k][0]>f[i][0]){
  29. f[i][0]=f[k][1];tempp=k;flag=1;
  30. }
  31. }
  32. if(flag==0) num[i][0]=num[tempp][1]+t[i]-t[tempp];
  33. else num[i][0]=num[tempp][0]+t[i]-t[tempp];
  34. //cout<<i<<" 0"<<' '<<num[i][0]<<' '<<f[i][0]<<endl;
  35. tempp=0;flag=1;
  36. for(int k=1;k<=i;k++){
  37. int temp=f[i][1];
  38. if(num[k][0]+t[i]-t[k]>=b[i])
  39. if(f[k][0]+1>f[i][1]){
  40. temp=f[k][0]+1;tempp=k;flag=0;
  41. }
  42. if(num[k][1]+t[i]-t[k]>=b[i])
  43. if(f[k][1]+1>f[i][0]){
  44. temp=f[k][1]+1;tempp=k;flag=1;
  45. }
  46. }
  47. if(flag==0) {
  48. num[i][1]=num[tempp][0]+t[i]-t[tempp]-b[i];
  49. f[i][1]=f[tempp][0]+1;
  50. }
  51. else {
  52. num[i][1]=num[tempp][1]+t[i]-t[tempp]-b[i];
  53. f[i][0]=f[tempp][1]+1;
  54. }
  55. //cout<<i<<" 1"<<' '<<num[i][1]<<' '<<f[i][1]<<endl;
  56. }
  57. //cout<<f[1][1]<<' '<<f[2][1]<<' '<<f[3][1]<<' '<<f[4][1]<<' '<<f[5][1]<<' '<<f[6][1]<<endl;
  58. cout<<max(f[n][1],f[n][0])<<endl;
  59. return 0;
  60. }