我要招人

去企业版

首页 > 试题广场 >

单帧操作

[编程题]单帧操作

热度指数：940 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定n个数字的序列 $a_0,a_1,\dots 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\le n )$ 次，最后得到的整个序列的总和最大可以是 $m_k$

你需要求出 $m_1,m_2,...m_n$

示例1

输入

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]，都可以得
只能操作2次的时候，按次序操作位置1和位置3可以得到[3,3,5,5,5]，其他操作不会得到更优的结果，所以
能操作3次以上的时候可以得到的最优序列为[3,4,5,5,5]（依次操作位置1，位置2，位置3）,所以

备注:

算法知识视频讲解

嗯学

bfs+dp，滚动数组优化,dp[i][k][t]代表第k次操作i位置后，i处的值为t对应的最大总增量，中间的k可以用滚动数组优化成二维节省空间。用bfs可以跳过很多无效状态，所以效率应该更高一些

class Solution {
public:
    /**
     *
     * @param n int整型 数字个数
     * @param a int整型vector 待操作序列
     * @return int整型vector
     */
    
    vector<int> ans;
    struct Sta{ int pos, k, mx; };
    vector<int> solve(int n, vector<int>& a) {
        // write code here
        ans.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> q;
        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++;
            q.push({i, 1, t});
            dp[i][t]=max(dp[i][t], cnt*t-g);
            ans[0] = max(cnt*t-g, ans[0]);
        }
        for(int k = 1; k < n; ++k){
            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.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) q.push(Sta{j, kk+1, w});//保存状态
                    dp1[j][w]=max(dp1[j][w], cnt*w-g+dp[pos][mx]);//更新结果
                    ans[kk] = max(dp1[j][w], ans[kk]);
                }
                dp[pos][mx] = -1;//还原数组为-1，方便下一轮扩展用
            }
            swap(dp, dp1);
        }
        for(auto &x : ans) x+=sum;
        return ans;
    }
};

编辑于 2020-03-15 14:35:46 回复(0)

学问笃实生光辉

class Solution {
public:
    vector<int> solve(int n, vector<int>& a) 
    {
        int maxValue=0;
        vector<int>res;
        for(int i=0;i<n;i++)
        {
            maxValue=max(maxValue,a[i]);
        }
        vector<vector<vector<vector<int>>>>dp(n,vector<vector<vector<int>> >(n+1,vector<vector<int>>(2,vector<int>(maxValue+1,-1))));
        for(int i=0;i<n;i++)
            for(int j=0;j<=i+1;j++)
            {
                if(i==0)
                {
                    int t;
                    if(j==0)
                        dp[i][j][0][a[i]]=a[i];
                    if(j==1)
                    {
                        t=max(a[i],a[i+1]);
                        dp[i][j][1][t]=t;
                    }
                }
                else
                {
                    for(int k=0;k<=maxValue;k++)
                    {
                        int t;
                        if(dp[i-1][j][0][k]!=-1)
                        {
                            dp[i][j][0][a[i]]=max(dp[i][j][0][a[i]],dp[i-1][j][0][k]+a[i]);
                        }
                        if(dp[i-1][j][1][k]!=-1)
                        {
                            //前一项操纵做了，本项不操作，则a[i]与a[i-1]元素一样
                            dp[i][j][0][k]=max(dp[i][j][0][k],dp[i-1][j][1][k]+k);
                        }
                        if(j>=1&&dp[i-1][j-1][0][k]!=-1)
                        {
                            //前一项没有放，但是这一项要放，取a[i-1],a[i],a[i+1]的最大值
                            t=max(k,a[i]);
                            if(i+1<n)
                                t=max(t,a[i+1]);
                            dp[i][j][1][t]=max(dp[i][j][1][t],dp[i-1][j-1][0][k]-k+2*t);
                        }
                        if(j>=1&&dp[i-1][j-1][1][k]!=-1)
                        {
                            t=max(k,a[i]);
                            if(i+1<n)
                                t=max(t,a[i+1]);
                            dp[i][j][1][t]=max(dp[i][j][1][t],dp[i-1][j-1][1][k]-k+2*t);
                        }
                    }
                }
            }
            int num;
            for(int j=1;j<=n;j++)
            {
                num=0;
                for(int k=0;k<=maxValue;k++)
                {
                    if(dp[n-1][j][0][k]!=-1)
                        num=max(num,dp[n-1][j][0][k]);
                    if(dp[n-1][j][1][k]!=-1)
                        num=max(num,dp[n-1][j][1][k]); 
                }
                res.push_back(num);
            }
        return res;
    }
};

编辑于 2020-05-10 09:46:29 回复(0)

提交观点

问题信息

动态规划广度优先搜索(BFS)

难度：

2条回答 14收藏 3527浏览

通过挑战的用户

查看代码

colddrink

2022-01-04 20:52:42
陈墨瞳1995

2021-12-23 17:39:29
牛客70924...

2021-10-19 22:18:03
philos

2021-10-16 23:19:53
CroMarmot

2021-10-02 02:43:52

单帧操作

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题