【强训笔记】day2

NO.1

思路：如果小于等于1，费用为20，大于1，费用为20加上超过1的整数，不足1的部分按照1来算。

代码实现：

#include<iostream>
using namespace std;

int main()
{

	float a;
	char b;
	cin >> a >> b;
	int ans = 0;
	if (a <= 1)
		ans += 20;
	else
	{
		ans += 20;
		double c = a - 1;
		if (a - (int)c) ans += (int)c + 1;
		else ans +=(int)c;
	}

	if (b == 'y') ans += 5;
	
	cout << ans << endl;
	return 0;
}

NO.2

思路：dp，由于可以选择走一步或者走两步，所以我们最后的状态就是前一楼花的钱加上前一楼需要的钱和前两步花的钱和前两步需要的钱的最小值。
代码实现：

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int cost[N];
int dp[N];
int n;

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) cin >> cost[i];

	for (int i = 2; i <= n; i++)
		dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);


	cout << dp[n] << endl;
	return 0;
}

NO.3

思路：设置两个表示两个目标字符串下标的数字prev1和prev2，ret表示两个字符串之间的最小距离，如果输入的s等于目标字符串s1，那么就去找字符串s2，在更新距离，此时字符串s1的下标为i，如果输入的s等于目标字符串s2，那么就去找字符串s1，同样的更新距离，此时字符串s2的下标为i。
代码实现：

#include<iostream>
#include<string>

using namespace std;

int main()
{
	int n;
	string s1;
	string s2;
	string s;
	cin >> n;
	cin >> s1 >> s2;

	int prev1 = -1, prev2 = -1, ret = 0x3f3f3f;//表示无穷大
	for (int i = 0; i < n; i++)
	{
		cin >> s;
		if (s == s1)//去前面找最近的s2
		{
			if (prev2 != -1)
			{
				ret = min(ret, i - prev2);
			}
			prev1 = i;

		}
		else if(s==s2)//去前面找最近的s1
		{
			if (prev1 != -1)
			{
				ret = min(ret, i - prev1);
			}
			prev2 = i;
		}
	}

	if (ret == 0x3f3f3f)
		cout << -1 << endl;
	cout << ret << endl;

	return 0;
}