题解 | #单帧操作#

题目描述
给定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

方法一：动态规划解法

求解思路
对于本题要求的最大值等于数组的元素和加上每次操作后增加最多的大小。因此可以一开始就求出数组的元素和，然后用辅助数组dp[n][n]来进行相关求解。其中dp[i][j]代表每次操作位置i后，i处的值为j时对应的最大总增量。

图片说明

解题代码

class Solution {
public:
    vector<int> myans;
    struct Sta{ int pos, k, mx; };
    vector<int> solve(int n, vector<int>& a) {
        myans.resize(n, INT_MIN);
        int maxe = *max_element(a.begin(), a.end());
        vector<vector<int>> dp(201, vector<int>(201, -1)), dp1 = dp; // 声明辅助数组
        queue<Sta> myq; // 辅助队列，来进行相关位置的增量
        int sum = 0;
        for(int i = 0; i < n; ++i)
        {
            sum += a[i]; // 数组和
            int t = a[i], g = a[i], cnt = 1;
            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++;
            myq.push({i, 1, t});
            dp[i][t]=max(dp[i][t], cnt*t-g); // 动态规划思想
            myans[0] = max(cnt*t-g, myans[0]); // 初值，并记录结果
        }
        for(int k = 1; k < n; ++k)
        {
            int sz = myq.size();
            for(int i = 0; i < sz; ++i)
            {
                auto sta = myq.front(); myq.pop();
                int pos = sta.pos, kk = sta.k, mx = sta.mx; // 声明相关位置变量等
                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) myq.push(Sta{j, kk+1, w});//保存状态
                    dp1[j][w]=max(dp1[j][w], cnt*w-g+dp[pos][mx]);//更新结果
                    myans[kk] = max(dp1[j][w], myans[kk]);
                }
                dp[pos][mx] = -1;//还原数组为-1，方便下一轮扩展用
            }
            swap(dp, dp1);
        }
        for(auto &x : myans) x+=sum;
        return myans; // 返回结果即可
    }
};

复杂度分析
时间复杂度：遍历矩阵，两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：使用辅助矩阵，因此空间复杂度为 $O$ ( $图片说明$ )

方法二：基于动态规划的优化求解

求解思路
基于方法一，我们可以给出其优化算法。我们添加一维变量用来记录位置i是否被操作，如果为0，则表示位置i操作了，如果为1，则表示位置i没被操作。并且结合方法一，我们可以得到本题的答案。

图片说明

解题代码

class Solution {
public:
     int mydp[205][205][205][2]; // 声明四维数组
     vector<int> solve(int n, vector<int> a){
        int maxn = 205; // 声明与题目相关变量
        int inf = 0x3f3f3f3f;
        int myans = 0;
        for(int i = 0; i < n; ++i) myans += a[i];
        for(int i = 0; i < maxn; ++i)
            for(int j = 0; j < maxn; ++j)
                for(int k = 0; k < maxn; ++k)
                    mydp[i][j][k][0] = mydp[i][j][k][1] = -inf; // 基于方法一，动态规划，并且对第四维进行操作
        mydp[0][0][a[0]][0] = 0;
        mydp[0][1][a[0]][1] = 0;
        for(int i = 0; i < n-1; ++i)
        {
            for(int j = 0; j <= i+1; ++j)
            {
                for(int x = a[i]; x < maxn; ++ x)
                {   //对可能遇到的情况进行分类讨论，结合动态规划的思想
                    //00
                    mydp[i+1][j][a[i+1]][0] = max(mydp[i+1][j][a[i+1]][0], mydp[i][j][x][0]);
                    //01
                    if(x > a[i+1])
                    {
                        mydp[i+1][j+1][x][1] = max(mydp[i+1][j+1][x][1], mydp[i][j][x][0] + x-a[i+1]);
                    }else
                    {
                        mydp[i+1][j+1][a[i+1]][1] = max(mydp[i+1][j+1][a[i+1]][1], mydp[i][j][x][0]+a[i+1]-x);
                    }
                    //10
                    if(x > a[i+1])
                    {
                        mydp[i+1][j][x][0] = max(mydp[i+1][j][x][0], mydp[i][j][x][1]+x-a[i+1]);
                    }else
                    {
                        mydp[i+1][j][a[i+1]][0] = max(mydp[i+1][j][a[i+1]][0], mydp[i][j][x][1]+(a[i+1]-x)+(i+1>1)*(a[i+1]-x));
                    }
                    //11
                    if(x > a[i+1])
                    {
                        mydp[i+1][j+1][x][1] = max(mydp[i+1][j+1][x][1], mydp[i][j][x][1]+x-a[i+1]);
                    }else
                    {
                        mydp[i+1][j+1][a[i+1]][1] = max(mydp[i+1][j+1][a[i+1]][1], mydp[i][j][x][1]+(a[i+1]-x)+(i+1>1)*(a[i+1]-x));
                    }
                }
            }
        }
        int mx = 0;
        for(int k = 1; k <= n; ++k)
        {
            for(int i = 1; i < maxn; ++i)
                for(int j = 0; j < 2; ++j)
                    mx = max(mx, mydp[n-1][k][i][j]); // 保存最大元素
            a[k-1] = myans+mx;
        }
        return a; // 返回结果
    }
};

复杂度分析
时间复杂度：遍历矩阵，两层循环，因此时间复杂度为 $O$ ( $图片说明$ )，但是第四维数组使得本方法比方法一运行时间更短。
空间复杂度：使用辅助矩阵，因此空间复杂度为 $O$ ( $图片说明$ )