秋招突击——算法打卡——6/5——提高{(状态机模型)股票买卖、（单调队列优化DP）最大子序列和}——新做：{考试的最大困扰度}

提高

(状态机模型)股票买卖IV

• 上一次的思路总结，上次写的时候忘记总结了，现在重新画一下图
• 

思路分析

• 这道题是一个经典的状态机模型，具体分析如下，两种做状态以及对应的转换形式。
  

实现代码

• 一写代码就懵逼，不知道怎么定义边界值，是从零开始还是从一开始，要不要给边界赋值？都不知道，得找一个方法，一块解决掉。
• 忘记怎么用memset，需要好好整理一下。
  • memset是来自cstring的
  • memset（ptr，value，sizeof（））
• 写成了下面这样

#include 
#include 
#include 

using namespace std;

const int N = 10010;
const int K = 110;
int w[N],k,n;
int f[N][K][2];

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


    // 遍历所有的边界进行赋值
    memset(f, 0, sizeof(f));
//    for (int i = 0; i <= k; ++i) {
//        f[0][k][0]  = 0;
//        f[0][k][1]  = 0;
//    }
//    // 遍历所有零次交易的情况
//    for (int i = 0; i <= n; ++i) {
//        f[k][0][0] = 0;
//        f[k][0][1] = 0;
//    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            f[i][j][0] = max(f[i - 1][k][0] , f[i - 1][k][1] + w[i]);
            f[i][j][1] = max(f[i - 1][k][1] , f[i - 1][k-1][0] - w[i]);
        }
    }

    cout<<max(f[n][k][0],f[n][k][1])<<endl;
}

参考代码

• 大体是一样，但是有两个问题，分别
  • 最大值的确定
    • 最后肯定是全部都卖光的情况，手里没有持有股票才对，所以只需要比价状态0就行了
    • 最后有可能交易次数没有用光，所以可能要遍历最后一天所有交易次数的情况
• 关于初始化的问题
  • 因为有可能 是负数，所以最开始的初始值要是最小的。
  • 因为再交易过程中，交易天数会为0，同时交易次数也会为0，因为都存在-1的情况，所以要对两者进行判定
    • 在第零天第零次交易的情况下，自身的收益本身就是0，存在f[i-1][j-1][0]的情况

#include 
#include 
#include 

using namespace std;

const int N = 10010;
const int K = 110;
int w[N],k,n;
int f[N][K][2];

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


    // 遍历所有的边界进行赋值
    memset(f, INT_MIN, sizeof(f));
    for (int i = 0; i <= n; ++i) {
        f[i][0][0] = 0;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            f[i][j][0] = max(f[i - 1][k][0] , f[i - 1][k][1] + w[i]);
            f[i][j][1] = max(f[i - 1][k][1] , f[i - 1][k-1][0] - w[i]);
        }
    }
    int res = 0;
    for (int i = 0; i <= k; ++i) {
        res = max(res, f[n][i][0]);
    }
    cout<<res<<endl;
}

新作

考试的最大困扰度

• 题目链接

个人实现

• 最直白的思路，统计一下所有的相同的T或者F的数量，然后将之转成数字，就变成了52146
• 改变其中某一个数字，形成新的序列，然后比如说选中2，最终就变成了846.然后在选择其中的最大值。最为输出
• 这样的话情况太多了，遍历的情况太多了，不好弄。
• 序列问题，使用双指针？
• 左边指针固定，右边指针向右进行遍历，如果相同就不改变k，如果不同就改变k，然后知道返回最终结果为止。

class Solution {
public:
  int maxConsecutiveAnswers(string s, int k) {
    int n = s.size(),kTemp = k;
    int res = 0;
    for (int l = 0; l < n;l ++) {
        int r = l+1;
        while(r < n && (s[l] == s[r] || kTemp > 0)){
            if (s[l] != s[r]){
                kTemp --;
            }
            r ++;
        }
        res = max(res,r - l );
        // 重置并重新移动l
        while(l + 1 < n && s[l] == s[l + 1]) l++;
        kTemp = k;
    }

    kTemp = k;
    for ( int r = n - 1; r >= 0;r --) {
        int l = r - 1;
        while(l >= 0 && (s[l] == s[r] || kTemp > 0)){
            if (s[l] != s[r]){
                kTemp --;
            }
            l --;
        }
        res = max(res,r - l );
        // 重置并重新移动l
        while(r - 1 >= 0 && s[r] == s[r - 1]) r --;
        kTemp = k;
    }
    return res;
}
};

• 就算再来一遍，双指针，还是只能通过60个样例，不够。
  

参考思路

• 这道题我们用的思路是一致的，不过他是将这个问题分开，也是使用双指针的，但是是分别计算最长的F的序列和最长的T序列，然后再求两个最大值。
• 思路变化
  • sum表示区间中非目标值的字符个数
    • sum < k：说明可以使用的k个操作进行翻转
    • sum > k：说明不能使用的k个操作进行反转，这里要不断移动j，减少不合法的字符的个数。
• 其中第二段的思路我没有意识到，我这里做错了，我这里是直接移动到第一个与当前符号不一样的字符那里，是一个问题。
• 这个模板好好记一下！

#include 
#include 
#include 
using namespace std;

int maxConsecutiveAnswers1(string s, int k,char t) {
    int n = s.size();
    int res = 0;
    for (int l = 0,r = 0,sum = 0; r < n;r ++) {
        if (s[r] != t)  sum ++;
        while(sum > k){
            if (s[l] != t) sum --;
            l ++;
        }
        res = max(res , r - l + 1);
    }
    return res;
}

int maxConsecutiveAnswers(string s,int k){
    return max(
            maxConsecutiveAnswers1(s,k,'F'),
            maxConsecutiveAnswers1(s,k,'T')
               );
}

int main(){
    cout<<maxConsecutiveAnswers("TTFF",2)<<endl;
}

总结

• 关于状态机模型，大概写对了，但是没有抓住精髓，还是对于边界的初始化有问题，不过这次有点意识了。
  • 除了根据实际意义来看，0次操作的情况下，就是没有任何收益
  • 凡是存在了-1的情况的话，都需要进行初始化，防止访问0的边界
• memset，是来自于cstring，无论是几个维度的数据，都是使用的f + sizeof（f）
• 今天还不错，继续加油。