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