比赛 |
20160415 |
评测结果 |
WWWWWTWTTT |
题目名称 |
烤鸡翅 |
最终得分 |
0 |
用户昵称 |
sro dydxh orz |
运行时间 |
4.825 s |
代码语言 |
C++ |
内存使用 |
0.79 MiB |
提交时间 |
2016-04-15 11:45:34 |
显示代码纯文本
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<algorithm>
- #include<cmath>
- #include<cstring>
- using namespace std;
- const int maxn=25000;
- int n,a[maxn+10],b[maxn+10],num[maxn+10][2],t[maxn];
- int f[maxn+10][2];//sell or not
- int main(){
- freopen("wing.in","r",stdin);
- freopen("wing.out","w",stdout);
- scanf("%d",&n);
- for(int i=1;i<=n;i++){
- scanf("%d",&a[i]);
- t[i]=t[i-1]+a[i];
- }
- for(int i=1;i<=n;i++) scanf("%d",&b[i]);
-
- for(int i=1;i<=n;i++){
-
- int tempp=0;bool flag=1;
- for(int k=1;k<i;k++){
- if(num[k][1]+t[i]-t[k]>=b[i])
- if(f[k][1]>f[i][0]){
- f[i][0]=f[k][1];tempp=k;flag=0;
- }
- if(num[k][0]+t[i]-t[k]>=b[i])
- if(f[k][0]>f[i][0]){
- f[i][0]=f[k][1];tempp=k;flag=1;
- }
- }
- if(flag==0) num[i][0]=num[tempp][1]+t[i]-t[tempp];
- else num[i][0]=num[tempp][0]+t[i]-t[tempp];
- //cout<<i<<" 0"<<' '<<num[i][0]<<' '<<f[i][0]<<endl;
-
- tempp=0;flag=1;
- for(int k=1;k<=i;k++){
- int temp=f[i][1];
- if(num[k][0]+t[i]-t[k]>=b[i])
- if(f[k][0]+1>f[i][1]){
- temp=f[k][0]+1;tempp=k;flag=0;
- }
- if(num[k][1]+t[i]-t[k]>=b[i])
- if(f[k][1]+1>f[i][0]){
- temp=f[k][1]+1;tempp=k;flag=1;
- }
- }
- if(flag==0) {
- num[i][1]=num[tempp][0]+t[i]-t[tempp]-b[i];
- f[i][1]=f[tempp][0]+1;
- }
- else {
- num[i][1]=num[tempp][1]+t[i]-t[tempp]-b[i];
- f[i][0]=f[tempp][1]+1;
- }
- //cout<<i<<" 1"<<' '<<num[i][1]<<' '<<f[i][1]<<endl;
-
- }
-
- //cout<<f[1][1]<<' '<<f[2][1]<<' '<<f[3][1]<<' '<<f[4][1]<<' '<<f[5][1]<<' '<<f[6][1]<<endl;
- cout<<max(f[n][1],f[n][0])<<endl;
- return 0;
- }