本文主要是介绍【笔试训练】day11，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.游游的水果大礼包
思路：
枚举。假设最后的答案是x个a礼包，y个b礼包，得到一个式子：ans=a*x+b*y
我们可以枚举x的数量，这样就能变相的把y的求出来。呃这就是鸡兔同笼问题嘛
x最大的范围是多少呢？也就是a礼包最多能做多少个，即min(n/2,m)
代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
typedef long long LL;int main() {int n, m, a, b;cin >> n >> m >> a >> b;int k1 = min(n / 2, m);LL ans = 0;for (int i = 0; i <= k1; i++) {int nn = n - i * 2;int mm = m - i;int k2 = min(nn, mm / 2);ans = max(ans, (LL)a * i + b * k2);}cout << ans << endl;return 0;
}
2.买卖股票的最佳时机（二）
思路：
先求简单版本，再去看进阶。
首先是简单版本：用dp[i][0]表示第i天过后手里没有股票的最大收益，用dp[i][1]表示第i天过后手里有股票的最大收益.
对于第i天的状态一共有两个：
- 第i天过后手里没有股票的情况
第i天没有股票，有可能第i-1天有股票，但是今天卖掉了,收益+a[i],也有可能第i-1天也没有股票。
根据题意，这两种情况取一个最大值。所以dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][0])
- 第i天过后，手里有一支股票 .
第i天有股票，有可能是第i-1天没有股票，今天买的，所以收益-a[i].也有可能第i-1天有股票，但是今天不卖。
根据题意，这两种情况取一个最大值。所以dp[i][1]=max(dp[i-1][0]-a[i],dp[i-1][1])
最后的答案是dp[n][0]
代码1：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int dp[N][2];
int a[N];
int main() {int n;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];dp[1][0] = 0;dp[1][1] = -a[1];for (int i = 2; i <= n; i++) {dp[i][0] = max(dp[i - 1][1] + a[i], dp[i - 1][0]);dp[i][1] = max(dp[i - 1][0] - a[i], dp[i - 1][1]);}cout << dp[n][0];return 0;
}再来思考进阶。
进阶是要求空间复杂度为O(1),说明一个数组都不能开。也意味着，我们必须边读入边处理。
但是根据朴素版本的代码，我们可以知道，其实对于第i天的状态,它只会被第i-1天的状态影响。
于是我们可以用两个变量分别表示第i-1天的有票和没票的状态。再用两个变量表示第i天的有票和没票的状态。
每过一天，我们就迭代一下每一天的状态。
于是化简状态转移方程得：
a2 = max(b1 + x, a1);b2 = max(a1 - x, b1);a1 = a2;//迭代b1 = b2;a2就表示dp[i][0],a1表示dp[i-1][0],b1,b2同理。
代码1：
#include <iostream>
using namespace std;int main() {int n;cin >> n;int x;int a1 = 0;int a2 = 0;int b1 = 0;int b2 = 0;cin >> b1;b1 = -b1;//初始化第一天for (int i = 2; i <= n; i++) {cin >> x;a2 = max(b1 + x, a1);b2 = max(a1 - x, b1);a1 = a2;//迭代b1 = b2;}cout << a2 << endl;return 0;
}3.倒置字符串
思路：
首先就是不要考虑什么标点，这是假信息。
剩下得就是简单的反转字符串，再反转每个单词。数据也小，随便暴力。
代码：
#include <iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;int main() {string str;getline(cin, str);string ans;int n = str.size();reverse(str.begin(), str.end());for (int i = 1, j = 0; i < n; i++) {if ((str[i] == ' ' && str[i - 1] != ' ') || i == n - 1) {string t = "";if (i != n - 1) {t = str.substr(j, i - j);} else {t = str.substr(j, i - j + 1);}reverse(t.begin(), t.end());ans += t;ans += ' ';j = i + 1;}}cout << ans << endl;return 0;
}
这篇关于【笔试训练】day11的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
