题解 | #单帧操作#

题目：
给定n个数字的序列 $a_{0}a_{1},…a_{n-1}$ ，对位置i进行一次操作将使得 $a_{i-1},a_{i},a_{i+1}$ 都变成 $max(a_{i-1},a_{i},a_{i+1})$
特别的，对位置0进行操作将使得 $a_{0}$ 和 $a_{1}$ 都变成 $max(a_{0},a_{1})$
对位置 $n-1$ 进行操作将使得 $a_{n−2}$ 和 $a_{n−1}$ 都变成 $max(a_{n−2},a_{n−1})$
并且操作过位置i之后，位置0到i都不能再操作
设最多可以操作k(k≤n)次，最后得到的整个序列的总和最大可以是 $m_{k}$
你需要求出 $m_{1},m_{2},...m_{n}$
方法一：四维动态规划
定义： $dp[i][j][m][k]$ 表示第 $i$ 个位置进行第j次操作值为 $m$ 的情况下整个序列的值最多增加多少，最后一维为0表示位置i还没操作过，为1表示 $i$ 位置操作过
状态转移：考虑前i个位置进行j次操作，第 $i$ 个位置值为 $m$ 转移到->对前 $i+1$ 个位置进行 $j$ 或者 $(j+1)$ 次操作。
1.如果位置 $i+1$ 不进行操作，有两种转移：

位置 $i$ 没有操作过，那么不会对位置 $i+1$ 造成任何影响， $dp(i+1,j,a[i+1],0)=max(dp(i+1,j,a[i+1],0),dp(i,j,x,0))$
位置 $i$ 进行过操作，那么位置 $i-1$ 的数字和位置 $i$ 的数字一定是相等的（特殊考虑i=0,前面没有数字)。这个时候判断 $a[i+1]$ 和 $x$ 的大小，如果是 $x$ 较大，那么 $i+1$ 位置会变成 $x$ 并增加 $x-a[i+1]$ ，即 $dp(i+1,j,x,0)=max(dp[i+1,j,x,0),dp(i,j,x,1)+x-a[i+1])$ ,否则位置 $i$ 和位置 $i-1$ 的值都会变成 $a[i+1]$ ,(因为对位置i进行过操作)，增加 $2*(a[i+1]-x)$ 的贡献（对0特判） $dp(i+,j,a[i+1],0)=max(dp(i+1,j,a[i+1],0),dp(i,j,x,1)+(a[i+1]-x)+(i+1>1?1:0) *(a[i+1]-x))$

2.如果位置 $i+1$ 进行操作，那么也有两种转移：

位置i没有操作过，那么对 $i+1$ 的操作只能影响位置 $i$ ，判断一下 $a[i+1]$ 和 $x$ 之间的关系并转移即可。

如果是 $x$ 较大，那么i+1位置会变成 $x$ ，并增加 $x-a[i+1]$ ,即 $dp(i+1,j+1,x,1)=max(dp(i+1,j+1,x,1),dp(i,j,x,0)+x-a[i+1])$
否则 $dp(i+1,j+1,a[i+1],1)=max(dp(i+1,j+1,x,1),dp(i,j,x,0)+a[i+1]-x))$
位置 $i$ 进行过操作，那么对 $i+1$ 的操作可能会影响 $i$ 和 $i-1$ 两个位置。和上面 $i+1$ 不操作的分支2进行相同的讨论即可。如果是 $x$ 较大，那么 $i+1$ 位置会变成 $x$ 并增加 $x-a[i+1]$ 即 $dp(i+1,j+1,x,1)=max(dp(i+1,j+1,x,1),dp(i,j,x,1)+x-a[i+1])$
否则，位置 $i$ 和位置 $i-1$ 的值都会变成 $a[i+1]$ , $dp(i+1,j+1,a[i+1],1) = max(dp(i+1,j+1,a[i+1],1),dp(i,j,x,1)+(a[i+1]-x)+(i+1>1?1:0)*(a[i+1]-x))$

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 数字个数
     * @param a int整型一维数组 待操作序列
     * @return int整型一维数组
     */
    public int[] solve (int n, int[] a) {
        // write code here
        int sum = 0;
        //原数组的和
        for(int i = 0;i<n;i++){
            sum += a[i];
        }
        //dp[i][j][m][k]表示第i个位置进行j次操作值为m的情况下整个序列的值最多增加多少，最后一维为0表示位置i还没2操作，1表示位置i操作了
        int[][][][] dp = new int[200][201][201][2];
        //dp数组初始化
        for(int i =0;i<dp.length;i++){
            for(int j = 0;j<dp[0].length;j++){
                for(int m = 0;m<dp[0][0].length;m++){
                    for(int k = 0;k<dp[0][0][0].length;k++){
                        dp[i][j][m][k] = Integer.MIN_VALUE;
                    }
                }
            }
        }
        int[] ans = new int[n];
        dp[0][0][a[0]][0] = 0;
        dp[0][1][a[0]][1] = 0;
        //i枚举位置，j枚举操作次数
        for(int i = 0; i < n-1; ++i){
            for(int j = 0; j <= i+1; ++j){
                for(int x = a[i]; x < 201; ++ x){
                    //第i+1行
                    dp[i+1][j][a[i+1]][0] = Math.max(dp[i+1][j][a[i+1]][0], dp[i][j][x][0]);
                    //01
                    if(x > a[i+1]){
                        dp[i+1][j+1][x][1] = Math.max(dp[i+1][j+1][x][1], dp[i][j][x][0] + x-a[i+1]);
                    }else{
                        dp[i+1][j+1][a[i+1]][1] = Math.max(dp[i+1][j+1][a[i+1]][1], dp[i][j][x][0]+a[i+1]-x);
                    }
                    //10
                    if(x > a[i+1]){
                        dp[i+1][j][x][0] = Math.max(dp[i+1][j][x][0], dp[i][j][x][1]+x-a[i+1]);
                    }else{
                        dp[i+1][j][a[i+1]][0] = Math.max(dp[i+1][j][a[i+1]][0], dp[i][j][x][1]+(a[i+1]-x)+(i+1>1?1:0)*(a[i+1]-x));
                    }
                    //11
                    if(x > a[i+1]){
                        dp[i+1][j+1][x][1] = Math.max(dp[i+1][j+1][x][1], dp[i][j][x][1]+x-a[i+1]);
                    }else{
                        dp[i+1][j+1][a[i+1]][1] = Math.max(dp[i+1][j+1][a[i+1]][1], dp[i][j][x][1]+(a[i+1]-x)+(i+1>1?1:0)*(a[i+1]-x));
                    }
                }
            }
        }
        int mx = 0;
        for(int k = 1;k<=n;k++){
            for(int i = 0;i<=200;i++){
                for(int j= 0;j<2;j++){
                    mx = Math.max(mx,dp[n-1][k][i][j]);
                }

            }
            ans[k-1] = mx + sum;
        }

        return ans;
    }
}

复杂度：
时间复杂度：最外面两层循环时间复杂度是 $图片说明$ ,里面一层时间复杂度是 $图片说明$ 所以总的时间复杂度是 $图片说明$
空间复杂度：dp数组所占空间， $图片说明$

方法二：动态规划+滚动数组思想

最大值=数组a的元素和+每次操作后增加量的最大值。因此可以一开始就求出数组a的元素和，因此我们可以定义 $dp$ 数组， $dp[i][j]$ 代表每次操作位置 $i$ 后， $i$ 处的值为 $j$ 时对应的最大总增量。
状态转移方程为 $dp[i][j]=Math.max(dp[i][j],cnt*j-originSum);$
再借助队列做一个类似bfs的遍历，队列中记录的分别是元素下标、第几次操作、以当前元素为中的连续三个最大值。先用队列保存第一次在各个位置上操作后的结果， $k=1$ ，然后对于每次操作，从队列中取出元素，向后扩展，更新最大值。
设置两个 $dp$ ，其中 $dp$ 记录每次操作后的值,而 $dp1$ 是用来在bfs时找到当前操作的最大增加量，最后需要更新进 $dp$ 中， $dp1$ 的更新方式类似的 $dp$
第一次在各个位置操作后的 $dp$ 表：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 数字个数
     * @param a int整型一维数组 待操作序列
     * @return int整型一维数组
     */
    public int[] solve (int n, int[] a) {
        // write code here
       int[]ans=new int[n];
        //dp[i][j]表示每次操作i位置时i处的值j处对应的总增量
        int [][]dp=new int[n][201];
        //dp1用来在bfs中找到当前操作的最大增加量
        int[][]dp1=new int[n][201];
        for(int i=0;i<n;i++){
            Arrays.fill(dp[i],-1);
            Arrays.fill(dp1[i],-1);
        }
        Queue<Sta>q=new LinkedList<>();
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=a[i];
            int t=a[i],originSum=a[i],cnt=1;
            //i不是第一个数
            if(i>0){
                t=Math.max(a[i-1],t);
                originSum+=a[i-1];
                cnt++;
            }
            //i不是最后一个数
            if(i<n-1){
                t=Math.max(a[i+1],t);
                originSum+=a[i+1];
                cnt++;//元素个数，边界处两个，非边界处3个
            }
            //用队列保存第一次在各个位置上操作后的结果，k=1
            q.add(new Sta(i,1,t));
            //在i位置操作后，t是最大值处的增量
            dp[i][t]=Math.max(dp[i][t],cnt*t-originSum);
            ans[0]=Math.max(cnt*t-originSum,ans[0]);
        }
        //bfs，继续操作n-1次
        for(int k=1;k<n;++k){
            int size=q.size();
            //枚举第一次操作后的结果
            for(int i=0;i<size;i++){
                Sta sta=q.poll();
                int pos=sta.pos,kk=sta.k,max=sta.max;
                //枚举下一次的操作位置，以后的每次操作位置都是向后扩展
                for(int j=pos+1;j<n;j++){
                    int max2,originSum,cnt=2;//扩展状态
                    if(j==pos+1){//向后扩展一位时
                        max2=max;
                        originSum=2*max;
                    }
                    else if(j==pos+2){//向后扩展两位时
                        max2=Math.max(max,a[j]);
                        originSum=max+a[j];
                    }else{
                        max2=Math.max(a[j-1],a[j]);
                        originSum=a[j-1]+a[j];
                    }if(j<n-1){
                        max2=Math.max(a[j+1],max2);
                        originSum+=a[j+1];
                        cnt++;
                    }
                    if(dp1[j][max2]==-1)q.add(new Sta(j,kk+1,max2));//状态不存在时新建状态，保存状态
                    //更新状态
                    dp1[j][max2]=Math.max(dp1[j][max2],cnt*max2-originSum+dp[pos][max]);
                    ans[kk]=Math.max(dp1[j][max2],ans[kk]);
                }
                dp[pos][max]=-1;//还原数组为-1，方便下一轮扩展用
            }
            //用dp1更新dp
            int[][]temp=dp;
            dp=dp1;
            dp1=temp;
        }
        //ans数组的每个元素为增加量最大值+原数组的和
        for(int i=0;i<n;i++){
            ans[i]+=sum;
        }
        return ans;
    }
    //pos是元素位置索引，k是第几次操作，max是当前连续三个数的最大值
    public class Sta{
        int pos;
        int k;
        int max;
        public Sta(int pos,int k,int max){
            this.pos=pos;
            this.k=k;
            this.max=max;
        }
    }
}

复杂度：
时间复杂度：遍历 $dp$ 矩阵的时间， $图片说明$
空间复杂度： $dp$ 矩阵占用的空间, $图片说明$