你方有 (n) 个人,攻击力和血量都是 (1)。对方有 (a) 个普通人, (b) 个只有盾的,(c) 个只有嘲讽的,(d) 个有盾又有嘲讽的,他们的攻击力和血量都是无穷大。有盾的可以抵挡一次攻击,有嘲讽的必须先被杀掉,才能杀没有嘲讽的。
你方的 (n) 个人排成一排,从左向右依次出击,你知道它们每个是否有剧毒属性(即攻击力为无穷大)。
每次出击选定的对方是被色子控制的。问你能打败多少个对方人,求最大值和最小值。
数据组数 (leq 100),所有数据 (leq 1000)
Solution
考虑暴力模拟题意,开四个计数器记录四类对手分别剩下几个,然后从左到右读取己方序列,按规则选取攻击对象。在任何情况下,我们可以把有嘲讽的和没有嘲讽的分开处理。先处理有嘲讽的,等到有嘲讽的处理完毕以后再去处理没有嘲讽的。在接下来的讨论中,我们忽略嘲讽这一属性。
容易发现,己方的剧毒者既可以杀盾,也可以杀人;而己方的普通人只能杀盾。
如果要使得答案最大
- 如果这一次派出的是普通人,就让它杀掉一个盾,将它转化为一个普通人
- 如果这一次派出的是剧毒者,看是否还有普通人,如果有就杀人,否则就杀盾
如果要使得答案最小
- 如果这一次派出的是普通人,若还有普通人,什么也不做,否则去破盾(一开始想成这里直接什么也不做了)
- 如果这一次派出的是剧毒者,看是否还有盾,如果有就杀掉一个盾,否则才杀人
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,a,b,c,d;
char s[N];
int solve1(int a,int b,int c,int d) {
int ans=0;
for(int i=1;i<=n;i++) {
if(c+d>0) {
if(s[i]=='0') {
if(d>0) --d,++c;
}
else {
if(c>0) --c,++ans;
else if(d>0) --d,++c;
}
}
else {
if(s[i]=='0') {
if(b>0) --b,++a;
}
else {
if(a>0) --a,++ans;
else if(b>0) --b,++a;
}
}
}
return ans;
}
int solve2(int a,int b,int c,int d) {
int ans=0;
for(int i=1;i<=n;i++) {
if(c+d>0) {
if(s[i]=='1') {
if(d>0) --d,++c;
else if(c>0) --c,++ans;
}
else {
if(c==0) if(d>0) --d,++c;
}
}
else {
if(s[i]=='1') {
if(b>0) --b,++a;
else if(a>0) --a,++ans;
}
else {
if(a==0) if(b>0) --b,++a;
}
}
}
return ans;
}
signed main() {
int t;
cin>>t;
while(t--) {
cin>>n>>a>>b>>c>>d>>s+1;
cout<<solve1(a,b,c,d)<<" "<<solve2(a,b,c,d)<<endl;
}
}