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