当前位置: 首页 > 工具软件 > Fish Sync > 使用案例 >

Clam and Fish

东门新立
2023-12-01

点我跳转原题

解题思路

四种类型的情况如下

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 ++
当获得type 1时判断当前是否有机会消耗鱼饵
若有机会马上消耗掉,使cnt - -,fish ++
没机会即当前没有type 0给我们的机会,此时我们选clam做成鱼饵,鱼饵有机会在type 0中消耗 故 cnt ++


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;
}

另外

直播中说的我感觉理解起来会简单一些
获得type 2 和 type 3 直接选鱼fish++
获得type 0时,bait > 0 就 fish++,bait - -
获得type 1时,我们无脑抓clam 做成 bait 后面会说为什么
最后获得的鱼的总数就是fish + bait / 2

除2是因为type 1的时候我们无脑抓clam做成鱼饵,暂时不考虑抓鱼
理由是我们把除了type 0消耗掉的剩下的bait (对于type 1)我们可以用一半去抓鱼,一半做成clam 这样获得的收益是最大的

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 bait = 0;
		for( int i = 0 ; i < n ; i++ )
		{
			if(s[i]=='0')
            {
                if( bait > 0 )
				{
					fish++;
					bait--;
				}
            }
            else if(s[i]=='1')
            {
                bait++;
            }
            else fish++;//type 3 的情况直接选鱼 还有 type 2 的也是直接选鱼
		}
		fish += bait/2;
		printf("%d\n",fish);
	}
	return 0;
}
 类似资料:

相关阅读

相关文章

相关问答