宵暗的妖怪

题目描述

露米娅作为宵暗的妖怪，非常喜欢吞噬黑暗。

这天，她来到了一条路上，准备吞噬这条路上的黑暗。

这条道路一共被分为部分，每个部分上的黑暗数量为。

露米娅每次可以任取 连续的 未被吞噬过的 三部分，将其中的黑暗全部吞噬，并获得中间部分的饱食度。

露米娅想知道，自己能获得的饱食度最大值是多少？

输入描述:

第一行一个正整数，代表道路被分的份数。

第二行有个正整数，代表每一部分黑暗数量。

数据范围：

输出描述:

一个正整数，代表最终饱食度的最大值。

示例1

输入

复制

7
2 4 1 4 2 1 8

输出

复制

6

说明

选择[2,4,1]和[4,2,1]这两段即可。饱食度为4+2=6。

示例2

输入

复制

7
2 4 1 7 2 1 8

输出

复制

7

说明

选择[1,7,2]这一段即可。饱食度为7。

值得注意的是，若取两段进行吞噬，反而最多只能获得6的饱食度，并不是最大的。

在处理的过程中dp[i][0]表示没有被吞噬的时候的值

dp[i][1]表示被吞噬的值

分为两种情况，如果是没有被吞噬的情况下，可以取前一个的最大

如果是这一个点被吞噬，就要从前一个的前一个没有被吞噬的那个来加上a[i]

因为最终是求得最大值，这个最大值会出现在倒数第二个，因为在吞噬的过程中，只取中间部分的饱食度

当然通过代码可以看到在最后也可以输出 -> dp[n][0]

map <ll,ll> mp;
ll dp[maxn][2];
ll a[maxn];
int main()
{
    int n = read;
    for(int i=1;i<=n;i++) a[i]=read;
    for(int i = 2;i<=n-1;i++){
        dp[i][0] = max(dp[i-1][1] , dp[i-1][0]);
        dp[i][1] = dp[i - 2][0] + a[i];
    }
    cout<< max(dp[n-1][0],dp[n-1][1]) <<endl;
    return 0;
}

文章知识点与官方知识档案匹配，可进一步学习相关知识

算法技能树leetcode-动态规划22-括号生成7707 人正在系统学习中