秋招突击——6/24——复习{完全背包问题——买书，状态转换机——股票买卖V}——新作{两数相除，LRU缓存实现}

引言

• 今天知道拼多多挂掉了，难受，那实习就是颗粒无收了。整的我有点失神，难受，可能后面的日子不好过吧，没什么钱了，然后奖学金评定不一定能够评上！

• 后续好好准备秋招吧，实习暂时算是告一段落了，也不再去想了，加油吧！

• 其实本来主管面就面的不好，我不应该在报什么希望，怀疑会出现像二面一样的情况，觉得免得不好，但是最终给你过了，不可能的！那种毕竟是少数吧！兄弟，加加油吧！我尽力就好了！不要再难过了！

• 不要总是心存侥幸 ，还是得脚踏实地，尽可能完成自己的计划。

复习

完全背包问题——买书

• 上一次分析链接
• 二维背包问题
• 第一次讲买药的背包问题

思路分析

• 这里暂时没有理解那个转换公式，还是使用传统的分析方式再写一遍！

个人实现

#include <iostream>

using namespace std;

const int N = 1010,M = 5;
int p[M] = {
   0,10,20,50,100};
int n,f[5][N];


int main(){
   
    cin>>n;
    f[0][0] = 1;
    for (int i = 1; i <= 4; ++i) {
   
        for (int j = 0; j <= n; ++j) {
   
            for (int k = 0; k * p[i] <= n; k ++) {
   
                f[i][j] +=f[i - 1][j - k * p[i]];
            }
        }
    }
    cout<<f[4][n];
}

状态转换机——股票买卖V

状态机模型已经做过几道题目了，具体链接如下

• 状态机——股票买卖
• 之前还做过大盗阿福，但是没有了，不过无所谓。
• 上一次的思路分析

个人实现

• 状态转换机的关键是确定有哪几种状态，然后确定状态转移方程，也就是确定了动态规划的方程，最终确定最终的结果。

• 这道题和之前的题目，有不同，没有了限定股票交易次数，所以需要重新考虑一下

• 这里去除了一个维度，但是有一个问题，这个冷冻期应该怎么处理，感觉像我下面这样处理有问题。然后这里有多重情况，应该怎么计算？先试试看吧，先这样写吧，冷冻期不能执行任何操作！

这里有一个问题，如果某一个状态选中了对应的值，那么上一个状态就会影响下一个状态，这就不满足动态规划的基本要求了！

• 暂时只能写成这样了，关于冷冻状态还不知道怎么处理！

#include <iostream>
#include <cstring>
using namespace std;

const int N = 10010,D = -1;//定义D状态表示冷冻状态
int f[N][2];  // 0表示没有持有股票，1表示持有了股票
int w[N],n;


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

    // 向后进行遍历
    memset(f, size(f),INT_MIN);
    for (int i = 1; i <= n + 1; ++i) {
   
        f[i][0] = max(f[i - 1][0],f[i - 1][1] - w[i]);