【笔试训练】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 
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 
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 
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 
#include
#include
#include
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;
}