点我跳转原题
解题思路
四种类型的情况如下
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.
题目大意是要我们最优选择然后得到最优情况下鱼的数量
用逆推的方式，从右边的type推到左边
当获得type 3时直接选鱼，不要clam
当获得type 0时可以记为有机会把制作的鱼饵消耗掉 cnt + 1
当获得type 1时判断当前是否有机会消耗鱼饵
若有机会马上消耗掉，使cnt - 1，fish + 1
没机会即当前没有type 0给我们的机会，此时我们选clam做成鱼饵，鱼饵有机会在type 0中消耗 故 cnt + 1
AC代码
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main()
{/*ios::sync_with_stdio(false);cin.tie(0);*/int t;scanf("%d",&t);while(t--){int n;string s;scanf("%d",&n);cin>>s;int fish = 0;int chance_cnt = 0;for( int i = n-1 ; i >= 0 ; i-- ){if(s[i]=='0'){chance_cnt++;}else if(s[i]=='1'){if(chance_cnt > 0){chance_cnt--;fish++;}else chance_cnt++;}else fish++;//type 3 的情况直接选鱼 还有 type 2 的也是直接选鱼}printf("%d\n",fish);}return 0;
}