题解 | #单帧操作#

题目：单帧操作
描述：给定n个数字的序列a0,a1,…an−1，对位置i进行一次操作将使得ai−1,ai,ai+1都变成max(ai−1,ai,ai+1)，特别的，对位置0进行操作将使得a0和a1都变成max(a0,a1)，对位置n-1进行操作将使得an−2和an−1都变成max(an−2,an−1)，并且操作过位置i之后，位置0到i都不能再操作。
设最多可以操作k(k≤n)次，最后得到的整个序列的总和最大可以是mk​
你需要求出m1,m2,...mn
实例一：输入：5,[1,2,3,4,5]，返回值：[18,21,22,22,22]
说明：输入：n=5, 输入序列为[1,2,3,4,5]
[1,2,3,4,5]对应位置0,1,2,3,4
只能操作1次的时候，对位置1操作得到[3,3,3,4,5]，或者对位置2操作可以得到[1,4,4,4,5]，或者对位置3操作可以得到[1,2,5,5,5]，都可以得m1=18。
只能操作2次的时候，按次序操作位置1和位置3可以得到[3,3,5,5,5]，其他操作不会得到更优的结果，所以m2=21。
只能操作3次以上的时候可以得到的最优序列为[3,4,5,5,5]（依次操作位置1，位置2，位置3）,所以m3=22,m4=22,m5=22。

解法一：
思路分析：首先我们分析题目的意思，因为看一眼文字又多又复杂，我们进行简便叙说，在给定的n个数字序列中有a0,a1,…an−1，我们需要对数字进行操作，使得位置i的连续三个位置的数字变成这三个数字的最大值，因为最开始的位置0和最后一个位置n - 1只有两个连续的数字，所以这两个位置的数字只需要变成两个数字的最大值，题目的大致意思就是这么简单，题目中询问的是最多可以操作k次，k < =n，最后得到的整个序列的总和最大可以是多少？题目要求计算对应的m1，m2，一直到mk。
实例分析：输入：5,[1,2,3,4,5]
因为该数组中分别对应的位置为0,1,2,3,4，所以我们进行分析：
第一轮：

第二轮：

——其余可自己模拟。
第三轮：

——第四轮第五轮省略和第三轮的结果值相同，所以最终输出的结果为[18,21,22,22,22]。
——根据上述分析，我们可以采用暴力法进行计算，首先设定一个存储容器res，最终返回的数组也存在该容器当中，设定两个指针对象i和j，i表示需要循环的次数和操作k次的轮回，j表示从0到n处理数据，放入变化的值，更新存入的数值，再通过一个累加操作，便可以测算出最大的值，i的循环因为需要不断的变化，需要操作k次，所以采用二进制的变换，1 << n表示n的二进制位左移一位，然后再次判断。
C++核心代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 数字个数
     * @param a int整型vector 待操作序列
     * @return int整型vector
     */
    vector<int> solve(int n, vector<int>& a) {
        // write code here
        vector<int> res(n, 0);//创建一个存储容器
        for(int i = 1; i < (1 << n); i++){//循环所有的可能性，1 << n表示n的二进制往左移动一位
            int count = 0;
            vector<int> value = a; //设定容器保存改变的值
            for(int j = 0; j < n; j++){
                if((i >> j) & true){
                    count++;
                    int maxnum = a[j];//设置最大值初始化
                    if(j - 1 >= 0)//在范围内计算最大的值，保存
                        maxnum = max(maxnum, value[j - 1]);
                    if(j + 1 < n)
                        maxnum = max(maxnum, value[j + 1]);
                    if(j - 1 >= 0)//替换其他值
                        value[j - 1] = maxnum;
                    if(j + 1 < n)
                        value[j + 1] = maxnum;
                    value[j] = maxnum;
                }
            }
            int sum = 0;//计算的总和
            for(int j = 0; j < n; j++)
                sum += value[j];//累加
            res[count - 1] = max(res[count - 1], sum);
            //将res重新更新后返回
        }
        return res;
    }
};

——在该算法中，可能会由于运行时间过长而导致的不符合限定时间内执行完成。其for循环采用二进制位左移一位判断，其内部还有一个更新的循环，所以其时间复杂度为，需要额外的存储空间，记录修改的值和保存的每轮循环的最大值，所以其空间复杂度为。
解法二：
思路分析：因为上述方法运行速度过长，但是有助于我们理解，其次我们分析，在上述方法中存在很多其实不需要判断的语句，当一个轮回中的最大值计算出来以后，其实有些是不需要再次计算，因为很明显它的值不会大于最大值。所以在此过程中，我们可以采用BFS的思想来判断某些不需要的可以跳过的操作。最后我们使用dp[i][k][t]数组，该数组表示第k次操作i位置后，i处的值为t对应的最大增量。
——首先我们需要设定一个结构体对象Sta，用来保存三个变量，设定一个res的存储容器，初始化的过程中给它重新分配大小空间，然后通过循环指针i来替换最大值变量，替换之后存入队列，保存好以后，循环判断m1到mk之间的大小值，并作数组的更新和容器的更新，最后更新完成之后，再次初始化数组为-1，重新开始新一轮的判断，以此循环，就能得到最终的序列。
C++核心程序为：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 数字个数
     * @param a int整型vector 待操作序列
     * @return int整型vector
     */
    vector<int> res;//设置最终存储的容器
    struct Sta{ //结构体对象，其中pos为位置，k为第k次，max为最大增量
        int pos, k, max;
    };
    vector<int> solve(int n, vector<int>& a) {
        // write code here
        res.resize(n, INT_MIN);//重新设定容器大小
        vector<vector<int>> dp(201, vector<int>(201, -1)), dp1 = dp;
        //设定一个初始化为-1的两层容器
        queue<Sta> q;
        int sum = 0;
        for(int i = 0; i < n; ++i){
            sum += a[i];
            int t = a[i], g = a[i], cnt = 1;//设定两个值t和g，t为同步的最大值
            if(i > 0) 
                t = max(a[i-1], t), g += a[i-1],cnt++;
            if(i < n - 1) 
                t = max(a[i+1], t), g += a[i+1], cnt++;//变换t
            q.push({i, 1, t});//将该数据入队列
            dp[i][t] = max(dp[i][t], cnt * t - g);//更换最大值
            res[0] = max(cnt * t - g, res[0]);
        }
        for(int k = 1; k < n; ++k){//循环k次，相当于判断m1到mk
            int sz = q.size();//队列的大小
            for(int i = 0; i < sz; ++i){
                auto sta = q.front(); //第一个元素赋值
                q.pop();
                int pos = sta.pos, kk = sta.k, mx = sta.max;//三种状态
                for(int j = pos + 1; j < n; ++j){//循环判断三个位置
                    int w, g, cnt = 2;
                    if(j == pos + 1) 
                        w = mx, g = 2 * mx;
                    else if(j == pos + 2) 
                        w = max(mx, a[j]), g = mx + a[j];
                    else 
                        w = max(a[j - 1],a[j]), g = a[j - 1] + a[j];
                    if(j < n - 1) 
                        w = max(a[j + 1], w), g += a[j + 1], cnt++;
                    if(dp1[j][w] == -1) 
                        q.push(Sta{j, kk+1, w});//保存数据
                    dp1[j][w] = max(dp1[j][w], cnt * w - g + dp[pos][mx]);
                    //更新
                    res[kk] = max(dp1[j][w], res[kk]);//最大值更新
                }
                dp[pos][mx] = -1;//将数组还原，进行下一轮的判断
            }
            swap(dp, dp1);
        }
        for(auto &x : res)//循环累加
            x += sum;
        return res;
    }
};

——在该程序中，我们直接看第二个for循环，循环最大值为N，需要循环三次，所以其时间复杂度为，在该程序中，因为需要构造额外的内存空间来辅助计算，所以其空间复杂度为。