codefoce 416 B

清疚 2022-09-21 01:03 122阅读 0赞

/*codeforce 416 B*/
    # include<iostream>
    # include<cstdio>
    # include<cstring>
    # include<cmath>
    # include<cstdlib>
    # include<algorithm>
    using namespace std;
    const int N=100008;
    int s[N][8];
    int dp[N][8];
    int n,m;
    int main()
    {
        while(cin>>n>>m)
        {
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                   cin>>s[i][j];
                   memset(dp,0,sizeof(dp));
            int x=0;
            for(int i=1;i<=m;i++)
            {
                x=x+s[1][i];
                dp[1][i]=x;
            }
            x=0;
            for(int i=1;i<=n;i++)
            {
                x=x+s[i][1];
                dp[i][1]=x;
            }
            for(int i=2;i<=n;i++)
            {
                for(int j=2;j<=m;j++)
                {
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j])+s[i][j];
                }
            }
            for(int i=1;i<n;i++)
                cout<<dp[i][m]<<" ";
            cout<<dp[n][m]<<endl;
        }
        return 0;
    }
    /*动态规划：
    动态转移方程：
    dp[i][j]=max(dp[i-1][j],dp[i][j-1])+s[i][j];
    dp[i][j]代表第i副画第j个画家所用的最短时间
    因为第i个画家画的时间与第i+1画家画的时间有重叠，
    所以要比较第j个画家画第i-1副画时间与第j-1画家画第i副画的时间，
    如果大的就包括了小的所延长的时间，最终把大的时间值加上第j画家画第i副画的时间
    */

发表评论取消回复

表情：

评论列表（有 0 条评论，122人围观）

还没有评论，来说两句吧...

相关阅读

相关 416. 分割等和子集

给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

た入场券/ 2024年05月24日 01:37/ 0 赞/ 79 阅读

相关 416. 分割等和子集

416. 分割等和子集题目解析解题思路 01背包问题 1. 确定dp数组以及下标的含义 2. 确定递

﹏ヽ暗。殇╰゛Y/ 2023年10月16日 16:24/ 0 赞/ 25 阅读

相关 416. 分割等和子集

打卡!!!每日一题今天带着大家做一道相对比较难的题目，当然我会通过讲解01背包问题带着大家过渡一下。题目描述： > 给你一个只包含正整数的非空数组 nums

以你之姓@/ 2023年10月11日 18:18/ 0 赞/ 130 阅读

相关 416. 分割等和子集

题目： [416. 分割等和子集][416.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_t

ゝ一世哀愁。/ 2022年12月01日 15:43/ 0 赞/ 177 阅读

相关 codefoce 416 B

/codeforce 416 B/ include<iostream> include<cstdio> include<cstring>

清疚/ 2022年09月21日 01:03/ 0 赞/ 123 阅读

相关 416-回溯算法-排列树

解空间-排列树的理论原始序列的全排列。不同的排列方式。比如说1234有很多排列方式，所有的排列方式中，可能只有其中几种排列方式才满足题目的要求。举个例子：

待我称王封你为后i/ 2022年09月05日 01:39/ 0 赞/ 175 阅读

相关 leetcode 416. Partition Equal Subset Sum | 416. 分割等和子集（Java）

题目 [https://leetcode.com/problems/partition-equal-subset-sum/][https_leetcode.com_pro

你的名字/ 2022年09月02日 11:55/ 0 赞/ 163 阅读

相关 Codeforces Round #416 (Div. 2)

地址：[点我][Link 1] A. Vladik and Courtesy 模拟 include<iostream> using namespace

刺骨的言语ヽ痛彻心扉/ 2022年05月14日 02:07/ 0 赞/ 98 阅读

相关 Codefoces 977E - Cyclic Components——————dfs

Cyclic Components You are given an undirected graph consisting of n vertices and m ed

我会带着你远行/ 2022年04月05日 08:58/ 0 赞/ 124 阅读

相关 leetcode416. Partition Equal Subset Sum

题目要求 Given a non-empty array containing only positive integers, find if the array

太过爱你忘了你带给我的痛/ 2022年03月08日 13:26/ 0 赞/ 193 阅读