1 条题解
-
0
思路
talk is cheap,show me you code
Code
/* 关键观察: 如果B中有连续的1(例如111),那么A中必须至少有一个数在这些连续的1的范围内或可以通过分裂生成这些1 对于B中的孤立1(例如010),A中必须直接包含这个1或通过分裂生成它。 对于连续的0,A中不能有任何数在这些0的范围内,否则分裂后会污染这些0 贪心策略: 将B的字符串分割成若干段连续的1和0 对于每一段连续的1,我们需要选择A中的一些数来覆盖这些1。具体来说: 如果一段连续的1完全被1覆盖(即没有0),那么A必须包含所有这些1 如果一段连续的1中包含0,我们需要选择一些数使得可以通过分裂覆盖所有的1而不影响0。这通常需要在1的两端或中间选择一些数 */ #include<algorithm> #include<iostream> #include<cstring> using namespace std; typedef long long LL; const int N=1e5+10; int n; LL a[N],res; string s; void solve(int l,int r){ bool flag=false; //检查是否有0 for(int i=l;i<=r;i++){ if(s[i]=='0'){ flag=true; break; } } if(!flag){ //如果没有0,直接选所有1 for(int i=l;i<=r;i++){ res+=a[i]; } }else{ if(r-l+1==3){ //处理101情况 res+=min(a[l]+a[r],a[l+1]+min(a[l],0ll)+min(a[r],0ll)); return; } //选择两端的负数 if(a[l]<0) res+=a[l]; if(a[r]<0) res+=a[r]; flag=false; //检查中间是否有复数,并加上 for(int i=l+1;i<r;i++){ if(a[i]<0){ flag=true; res+=a[i]; } } if(!flag){ //如果没有负数,选择中间的最小值 LL minv=2e9; for(int i=l+1;i<r;i++){ minv=min(minv,a[i]); } res+=minv; } } } int main(){ int id,T; cin>>id>>T; while(T--){ cin>>n>>s; s=' '+s; res=0; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1,l=0,r=0;i<=n;i++){ if(s[i]=='1'){ r=i; if(!l) l=i; } //遇到两个连续的0或字符串结束,处理当前段 if((i==n||(s[i]=='0'&&s[i+1]=='0'))&&l!=0){ solve(l,r); l=0; } } cout<<res<<endl; } return 0; }
- 1
信息
- ID
- 137
- 时间
- 3000ms
- 内存
- 512MiB
- 难度
- 7
- 标签
- 递交数
- 209
- 已通过
- 47
- 上传者