`

【最大不连续子序列和】HDU 2845 Beans

阅读更多

KIDx的解题报告

 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2845

题意:在图中取数,例如取了81之后,同一行的相邻两个不能取,还有81的上面那行和下面那行也不能取,问能取到的最大和是多少?

 

解析:对于一行来说,相邻的数不可同时取,

容易得到状态转移方程:sum[i] = max (sum[i-2]+sum[i], sum[i-1])i>=2,注意i从1开始,i-2=0时不存在sum[i-2]相当于只取sum[i]),初始时sum[0] = 0, sum[i]就是第i个数

而对于一列来说,显然的也是相邻的不能取,所以对每一行处理完后再用每行得到结果组成一列进行同样处理即可得出答案

#include <iostream>
using namespace std;
#define M 200005

int a[M], b[M];

int main()
{
    int m, n, i, j;
    while (~scanf ("%d%d", &m, &n))
    {
        for (i = 1; i <= m; i++)
        {
            for (j = 1; j <= n; j++)
                scanf ("%d", b+j);
            for (j = 2; j <= n; j++)
                b[j] = max (b[j-2]+b[j], b[j-1]);
            a[i] = b[n];
        }
        for (i = 2; i <= m; i++)
            a[i] = max (a[i]+a[i-2], a[i-1]);
        printf ("%d\n", a[m]);
    }
    return 0;
}

 

 

  • 大小: 13 KB
1
0
分享到:
评论

相关推荐

    ACM HDU题目分类

    例如,1003 DP 经典问题,最大连续子段和;1024 经典 DP,最大 M 子段和;1025 经典 DP,最长递增子序列(要用 NLogN 的方法过);1051 经典贪心,也可以用 DP;1058 经典问题,丑数,DP;1081 经典 DP 等等。 搜索...

    HDU题目java实现

    9. **动态规划**:这是一种优化策略,通过构建状态转移方程来求解问题,例如背包问题、最长公共子序列、矩阵链乘法等。 10. **回溯法**:在解决组合优化问题和逻辑推理问题时常用,如八皇后问题、数独求解等。 11....

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    hdu 1257 最低拦截系统 lis

    题目名为“hdu 1257 最低拦截系统”,这里的“最低拦截系统”实际上是描述了一个问题场景,而具体的问题通过描述部分可以得知是要求找出给定数组中的最长递增子序列的长度。这里所谓的“最低拦截系统”可能是为了...

    HDU DP动态规划

    常见的DP题目类型包括但不限于最长公共子序列、背包问题、最短路径、区间调度等。 在动态规划中,我们通常遵循以下步骤: 1. **定义状态**:确定问题的状态,通常是问题的关键属性的组合。 2. **状态转移方程**:找...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    "hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届活动。这个压缩包可能是参赛者或教练分享的解题代码和资料。 【描述】提到的"水仙花数"问题,是计算机科学和算法竞赛中...

    hdu1250高精度加法

    1. **定义常量**:首先定义了两个最大值`max1`和`max2`,分别用于存储斐波那契数列的长度以及每个数的最大位数。 2. **定义数组**:定义了一个字符数组`f[max1][max]`用于存储每一项斐波那契数列的值。 3. **高精度...

    HDU acm-PPT课件

    对于特定问题,比如最大子序列和、最小覆盖子集等,需要掌握特定算法,如Kadane's algorithm或Dijkstra's algorithm。 四、数学基础:开启解题新维度 数学在ACM竞赛中扮演着重要角色,包括数论(模运算、同余方程...

    hdu动态规划算法集锦

    - 定义状态$sum[i]$表示以第$i$个元素结尾的最大连续子数组和。 - 状态转移方程:$sum[i] = \max(sum[i-1] + a[i], a[i])$。 - 最大值的计算可以通过维护一个变量`Max`来完成,遍历数组时不断更新`Max`的值即可。...

    ACM HDU

    2. **动态规划**:解决许多具有重叠子问题和最优子结构的问题,如背包问题、最长公共子序列等。 3. **贪心算法**:在每一步选择局部最优解,以期达到全局最优,如活动安排问题、霍夫曼编码等。 4. **数据结构**:...

    HDU 不容易系列之二 2042

    你活的不容易,我活的不容易,他活的也不容易。不过,如果你看了下面的故事,就会知道,有位老汉比你还不容易。

    杭电ACMhdu1163

    “hdu1163”是该问题在杭电ACM平台上的唯一标识符,方便选手查找和讨论。 【详细知识点】: 1. **算法基础**:解决ACM题目,首先需要掌握基础的算法,如排序(快速排序、归并排序、冒泡排序等)、搜索(二分查找、...

    HDU1059的代码

    HDU1059的代码

    hdu 300+ AC 代码

    在编程竞赛中,动态规划常用于解决背包问题、最长公共子序列、最短路径等问题。理解动态规划的状态转移方程和边界条件是掌握这一方法的关键。 这个压缩包中的300+ AC代码提供了丰富的示例,可以帮助学习者深入理解...

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    Hdu1000—2169部分代码

    3. **动态规划**:解决具有重叠子问题和最优子结构的问题。 4. **图论算法**:最短路径算法(Dijkstra、Floyd-Warshall)、拓扑排序、最小生成树(Prim、Kruskal)等。 5. **数学方法**:模运算、数论、组合数学等。...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    HDU 动态规划(46道题目

    - 特殊情况下,数组中的所有元素均为负数时,最大连续子序列和为数组中的最大元素。 - 可以使用更简洁的代码实现,如示例代码所示。 #### 四、LargestRectangle (最大矩形面积) **问题描述:** 本题要求在一组高度...

Global site tag (gtag.js) - Google Analytics