牛客春招刷题训练营 - 2025.4.29 题解

活动地址：牛客春招刷题训练营 - 编程打卡活动

Easy 游游的数字圈

简要题意

数一个十进制数里圆圈的个数。

Solution

逐位计数即可。

Code

void R()
{
	auto cnt=[&](int x)->int
	{
		if (x==8) return 2;
		if (x==0||x==6||x==9) return 1;
		return 0;
	};

	int ans=0;
	string s;
	cin>>s;
	for (char c:s) ans+=cnt(c-'0');
	cout<<ans;
	return;
}

Medium 最小花费爬楼梯

简要题意

起初在第 层，第 层可以消耗 的代价向上爬 层，求爬到 层的最小代价。

Solution

记 为第 层方案数，有转移：

即为答案。

Code

void R()
{
	constexpr i64 inf=1e18;
	int n;
	cin>>n;
	vector<i64> a(n),dp(n+1,inf);
	for (i64 &x:a) cin>>x;
	
	dp[0]=dp[1]=0;
	for (int i=2;i<=n;i++)
		dp[i]=min(dp[i-1]+a[i-1],dp[i-2]+a[i-2]);
	cout<<dp.back();
	return;
}

Hard 取数游戏

简要题意

给两个长度为 的数组 ，每次可以从 的左/右端取出一个数，第 次取出数 则产生 的贡献，求贡献最大值。

Solution

设 表示剩 待取的最大贡献，有转移：

即为答案。

Code

void R()
{
	int n;
	cin>>n;
	vector<int> a(n),b(n);
	vector<vector<int>> dp(n,vector<int>(n));
	for (int &x:a) cin>>x;
	for (int &x:b) cin>>x;

	auto dfs=[&](auto &self,int l,int r)->int
	{
		if (l>r) return 0;
		if (dp[l][r]) return dp[l][r];
		int now=l-r+n-1;
		return dp[l][r]=max(self(self,l+1,r)+a[l]*b[now],self(self,l,r-1)+a[r]*b[now]);
	};

	cout<<dfs(dfs,0,n-1);
	return;
}