1 条题解
-
0
#include<bits/stdc++.h> using namespace std; int js_n;//僵尸的种数 int js_m[110];//每种僵尸花多少钱 int js_p[110];//每种僵尸的攻击力 int zw_n;//植物的行数 int zw_m[210000];//每行植物"最少"需要多少钱才能被击破 int zw_p[210000];//每行植物需要多少攻击力才能被击破 int M,m_p[1005]; //钱的总数、m_p[7]表示7块钱能产生的攻击力 int f[210000];//f[i]表示打掉一段植物[?,i]的总花费 int main() { scanf("%d%d%d",&js_n,&zw_n,&M); for(int i=1;i<=js_n;i++)scanf("%d",&js_m[i]); for(int i=1;i<=js_n;i++)scanf("%d",&js_p[i]); for(int i=1;i<=zw_n;i++) scanf("%d",&zw_p[i]); //zw_m[i]=?? memset(m_p,0,sizeof(m_p));m_p[0]=0; for(int i=1;i<=js_n;i++) for(int j=js_m[i];j<=M;j++) m_p[j]=max( m_p[j] , m_p[ j-js_m[i] ] + js_p[i] ); for(int i=1;i<=zw_n;i++) { zw_m[i]=M+1; for(int j=0;j<=M;j++) if(zw_p[i]<=m_p[j]) { zw_m[i]=j; break; } /* int L=0,R=M,ans=M+1; while(L<=R) { int mid=(L+R)/2; if(m_p[mid]>=zw_p[i]) ans=mid,R=mid-1; else L=mid+1; } zw_m[i]=ans; */ } /* int st=-1,ed=-1,ans=0; f[0]=0; for(int i=1;i<=zw_n;i++) { if(zw_m[i]<=M) { f[i]=f[i-1]+zw_m[i]; if(st==-1)st=i; ed=i; while(f[i]>M) f[i]-=zw_m[st],st++; ans=max(ans,ed-st+1); } else f[i]=0,st=ed=-1; } printf("%d\n",ans); */ int sm=0,ans=0; deque<int> Q; for(int i=1;i<=zw_n;i++) { if(zw_m[i]<=M) { sm+=zw_m[i]; Q.push_back(i); while(sm>M) sm-=zw_m[ Q.front() ] ,Q.pop_front(); int tmp=Q.size(); ans=max( ans , tmp ); } else sm=0,Q.clear(); } printf("%d\n",ans); return 0; }
- 1
信息
- ID
- 254
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 5
- 标签
- 递交数
- 77
- 已通过
- 32
- 上传者