题意

长度为$nn$的数组, 每次把相邻的三个数，都变为它们中的最大值，操作的下标从左向右

问，操作$ii$次后的数组的最大和, 其中$ii$从$11$取到$nn$,给出不同$ii$对应的最大值。

$n\le 200n\backslash leq\; 200$

数组中每个数值$11$到$200200$之间的整数

算法

深搜(TLE)

我们使用深度优先搜索来实现题意

dfs(该轮搜索起始下标idx，操作过的次数cnt, 当前总和或当前增量s) 以及一个全为0的最大值数组

每一次深度优先搜索函数调用，从上一次调用中传递过来的搜索起始坐标开始，遍历下标$i=idx\mathrm{.}\mathrm{.}ni\; =\; idx..n$

如果不操作位置$ii$，继续遍历下标。

如果操作位置$ii$，把对应位置现有值保存，根据题意处理值，递归调用到下一层，调用后恢复保存的值 并继续遍历下标

在每一层深搜的时候都去更新最大值。最终深搜完后，最大值数组就是答案。

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 数字个数
# @param a int整型一维数组 待操作序列
# @return int整型一维数组
#
class Solution:
    ans = []
    def dfs(self, n, a, idx, cnt, s): # 下标 次数，增量
        self.ans[cnt] = max(self.ans[cnt], s)
        if idx == n:
            return
        for i in range(idx,n):
            # 操作 i
            old = [a[i-1] if i > 0 else 0,a[i],a[i+1] if i+1 < n else 0]
            maxv = max(old)
            der = maxv - a[i]
            a[i] = maxv
            if i > 0:
                der += maxv - a[i-1]
                a[i-1] = maxv
            if i+1 < n:
                der += maxv - a[i+1]
                a[i+1] = maxv
            self.dfs(n,a,i+1,cnt+1,s+der)
            # 恢复
            a[i] = old[1]
            if i > 0:
                a[i-1] = old[0]
            if i+1 < n:
                a[i+1] = old[2]
                
    def solve(self , n , a ):
        self.ans = [0 for i in range(n+1)]
        sa = sum(a);
        self.dfs(n,a,0,0,0)
        return [sa + v for v in self.ans[1:]]

复杂度分析

空间复杂度: 递归深度最大是数组长度，记录结果的有一个数组维护，这两个都是与原数组长度一致，所以空间复杂度$O(n)O(n)$

时间复杂度: 通过递归，相当于把所有方案都搜索了一遍，而每个位置操作和不操作两种可能，所以时间复杂度为$O(2^n)O(2^n)$ 无法通过

递推/动态规划

考虑动态规划，那么开始设计状态，先看必备的状态成分，我们要求的是所有次数的最大值，因此 下标 和 操作次数 是跑不了的

也就是$dp[\mathrm{下}\mathrm{标}][\mathrm{操}\mathrm{作}\mathrm{次}\mathrm{数}]dp[下标][操作次数]$, 目前来说这个状态最大限度是$200\ast 200=40000200\; *\; 200=40000$

那么当达到一个位置，跟这个位置有关的信息还有

1. 最大值，根据最大的限度可以达到$n\ast max(a_i)=40000n\; *\; max(a\_i)\; =\; 40000$
2. 上一个位置数的值, 根据范围是$max(a_i)=200max(a\_i)\; =\; 200$
3. 当前位置数的值,根据范围是$max(max(a_i)-a_i)=200max(max(a\_i)\; -\; a\_i)\; =\; 200$

首先最大值上限太高，不会作为状态，肯定排除了

上一个数的值应该是必要的，所以现在可能的运算上限是$40000\ast 200=800000040000\; *\; 200\; =\; 8000000$

当前位置数的值也需要，但是使用值的话，范围肯定超了

注意到，当前位置要么是$a[i]a[i]$本身（操作了没变或者没有操作），要么和上一个值一样（因为受到操作影响），所以我们不需要增加当前位置数的值的状态，而是增加一个是否操作了的状态，从而推出当前位置的值

综上，状态设计为

$dp[\mathrm{下}\mathrm{标}][\mathrm{对}\mathrm{应}\mathrm{的}\mathrm{值}][\mathrm{是}\mathrm{否}\mathrm{操}\mathrm{作}\mathrm{过}][\mathrm{总}\mathrm{操}\mathrm{作}\mathrm{数}]=\mathrm{最}\mathrm{大}\mathrm{增}\mathrm{量}dp[下标][对应的值][是否操作过][总操作数]\; =\; 最大增量$

那么有递推关系

$dp[idx][value][op][opcnt]dp[idx][value][op][opcnt]$

其中$idxidx$的关系是朴素的$+1+1$，而$opcntopcnt$的关系是朴素的$+op+op$

稍微复杂的是$valuevalue$的取值，见下表

最后增量的计算：

如果没有操作，那么增量不变,

如果操作了，那么增加的是，新的value- 之前三个位置上的value

当我们计算完了所有$dpdp$的值后

那么题目要求的答案，例如操作$kk$次，则为$dp[n][0\cdots 200][true\mathrm{/}false][k]+\sum a_{i}dp[n][0\backslash cdots200][true/false][k]\; +\; \backslash sum\; a\_i$ 中的最大值

可以在$O(n)O(n)$ 输出答案

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 数字个数
     * @param a int整型vector 待操作序列
     * @return int整型vector
     */
    vector<int> solve(int n, vector<int>& a) {
        const int INF = 0x3f3f3f3f;
        // dp[i位置(滚动下标)][i的值][i是否操作][操作总数] = 最大增量
        vector<vector<vector<vector<int>>>>
            dp(2,vector<vector<vector<int>>>(201,vector<vector<int>>(2,vector<int>(n+1,-INF))));
        // [滚动下标][上一个位置的值][操作作次数]，总和最大值
        dp[0][0][0][0] = 0;
        for(int i = 1;i <= n;i++){
            // clear
            for(int v = 0;v <= 200;v++){
                for(int op = 0;op<=i;op++){
                    for(int vis=0;vis<2;vis++){
                        dp[i%2][v][vis][op] = -INF;
                    }
                }
            }
            for(int v = 0;v <= 200;v++){
                for(int op = 0;op<= i-1;op++){
                    for(int vis = 0 ;vis<2;vis++){
                        // 上一个值 为v，操作状态vis，总操作次数op，最大增量 不为-INF
                        if(dp[(i-1)%2][v][vis][op] == -INF)continue;
                        // v, oldx , a[i]
                        int oldx = vis?v:a[i-1]; // 当前的值
                         // 不操作
                        int x = oldx; // 新的值 增量不变
                        dp[i%2][x][0][op] = max(dp[i%2][x][0][op],dp[(i-1)%2][v][vis][op]);
                        // 操作 新的值为x
                        x = i==1?x:max(x,v);
                        x = i==n?x:max(x,a[i]);
                        // 增量
                        int inc = x-oldx;
                        inc += i==1?0:(x-v);
                        inc += i==n?0:(x-a[i]);
                        dp[i%2][x][1][op+1] = max(dp[i%2][x][1][op+1],dp[(i-1)%2][v][vis][op] + inc);
                    }
                }
            }
        }
        vector<int>ans;
        int suma = 0;
        for(auto v:a){
            suma+=v;
        }
        for(int op = 1;op<=n;op++){
            int maxans = 0;
            for(int v= 0;v<=200;v++){
                for(int vis = 0 ;vis<2;vis++){
                    maxans = max(maxans,dp[n%2][v][vis][op]);
                }
            }
            ans.push_back(maxans+suma);
        }
        return ans;
    }
};

复杂度分析

空间复杂度: 除了答案的$O(n)O(n)$空间，我们核心是使用了设计的状态来储存，空间复杂度和状态占用一致是$O(n^2\cdot max(a_i))O(n^2\; \backslash cdot\; max(a\_i))$, 因为在递推关系中，仅与上一次的值有关，这里用了滚动数组来减少下标的维度，所以空间复杂度为$O(n\cdot max(a_i))O(n\; \backslash cdot\; max(a\_i))$

时间复杂度: 操作分为三部分，状态计算，求a的总和，提供答案，后面两部分明显只需要$O(n)O(n)$即可完成，主要是状态计算。我们对于状态的遍历是$\mathrm{下}\mathrm{标}(n)\cdot \mathrm{值}(max(a_i))\cdot \mathrm{是}\mathrm{否}\mathrm{操}\mathrm{作}(2)\cdot \mathrm{操}\mathrm{作}\mathrm{总}\mathrm{数}(n)下标(n)\backslash cdot\; 值(max(a\_i))\; \backslash cdot\; 是否操作(2)\backslash cdot\; 操作总数(n)$, 对于一个具体的状态，转移代价是常数，所以总时间复杂度为 $O(n^2\cdot max(a_i))O(n^2\; \backslash cdot\; max(a\_i))$