• The game contains n stages, numbered from 1 to n
• There are four types of stages(numbered from 0 to 3):
  • type 0: There are no fish and no clam in this stage.
  • type 1: There are no fish and one clam in this stage.
  • type 2: There are one fish and no clam in this stage.
  • type 3: There are one fish and one clam in this stage

In each stage,you can do exactly one of the following four actions.

1. If there is a clam in the stage,you can use this clam to make one pack of fish bait. And the number of packs of fish bait you have is increased by one . You can use this pack of fish bait to catch fish after this stage.
2. If there is one fish in the stage,you can catch this fish without any fish bait. After this stage,the number of packs of fish bait you have is not changed.
3. If you have at least one pack of fish bait. You can always catch one fish by using exactly one pack of fish bait even if there are no fish in this stage. After this stage, the number of packs of fish bait you have is decreased by one.
4. You can do nothing.

Now ,you are given n and the type of each stage. Please calculate the largest number of fish you can get in the fishing game.

输入描述

The first line contains one integer t(\(1\leq t \leq 2.5\times 10^{5}\)) ---the number of test cases.

There are two lines in each test. The first line contains one integer n (\(1\leq n \leq 2\times 10^{6}\)) . indicating the number of stages in this game. The second line contains a string with length n. The i-th character of this string indicates the type of the i-th stage.

The sum of n across the test cases doesn't exceed 2\(\times\) \(10^{6}\) .

输出描述

For each test case print exactly one integer -- the maximum number of fish you can catch in the game configuration.

示例1

输入

2
4
0103
1
1

输出

2
0

题解

#include<iostream>
#include<cstring>
using namespace std;
char num[2000005];//存放状态的字符串 
int main(){
    int N;//状态字符串的长度 
    scanf("%d",&N);
    while(N--){
        int fish=0;//初始化鱼为0 
        int bait=0;//初始化鱼饵为0 
        int change=0;//初始化使用鱼饵的机会为0 
        int len;
        scanf("%d",&len);
        getchar();//输入字符时要注意的事项，吞掉回车键
        //输入状态字符串 
        for(int i=0;i<len;++i){
            scanf("%c",&num[i]);
            if(num[i]=='0'||num[i]=='1'){
                change++;
            } 
        }
        //吞掉回车键 
        getchar();
        //从头遍历状态字符串 
        for(int i=0;i<len;++i){
            //如果有鱼，就抓鱼 
            if(num[i]=='2'||num[i]=='3'){
                fish++;
            }
            //如果没鱼，并且有蛤蜊，当鱼饵数量小于使用鱼饵的机会时，
            //把此时的蛤蜊制作成鱼饵保存着，鱼饵加1 
            //每经历一次0或1阶段，使用鱼饵的机会就减少1 
            else if(num[i]=='1'&&bait<change){
                bait++;
                change--; 
            }
            //其他情况下，只要有鱼饵，就使用鱼饵
            //使用鱼饵后，鱼加1，鱼饵减1，
            //经历一次0或1阶段后，使用鱼饵的机会减1 
            else{
                if(bait>0){
                    fish++;
                    bait--;
                }
                change--;
            }
        }
        //照此贪心的做法，最后得出的鱼的数量就是最大的 
        printf("%d\n",fish);
    }
    return 0;
}

这题我是按贪心的做法来做的，有鱼的时候抓鱼一定最优，主要就是看没鱼的时候怎么办，没鱼的情况分两种，一种是有蛤蜊，一种是没蛤蜊，在有蛤蜊的情况下，到底是把当前的蛤蜊抓起来做成鱼饵，还是使用背包里的鱼饵来获得鱼呢？这是需要考虑的，我的做法是提前遍历一遍状态字符串，来获得总共有多少次机会能使用鱼饵。通过前面的分析，我们发现，只有为0阶段或1阶段时，我们才可能使用鱼饵。所以只要遍历到0或1阶段的状态，就把使用鱼饵的机会加1。

使用鱼饵的机会将成为我们决策的重要指标，当我们处于没鱼有蛤蜊的情况下，如果此时背包里鱼饵的数量小于能使用鱼饵的机会的话，我们就把当前池塘里的蛤蜊制作成鱼饵，所以鱼饵加1。也就是说，我还有大把的机会能使用鱼饵，那我就不在这使用鱼饵，而是制作鱼饵，这样鱼饵的数量就多了，然后我在后面的机会中使用鱼饵，那这就是最优的了。如果此时背包里鱼饵的数量大于等于使用鱼饵的机会的话，那就要马上使用鱼饵了，因为再不使用就没机会使用了，那样就会造成浪费了。

当既没鱼也没鱼饵的时候，就只能看当前的背包里是否有鱼饵可以使用了，如果有那就使用，没有就什么也不做。

照着这个贪心的思想来一步步的走，最后得到的鱼的数量就是最优的。