1083 AlvinZH的青春记忆I

思路

中等题，动态规划。

简化题意，一个环上取数，数不可相邻，取取得数之和最大值。

环不好表示，可以解开变成一列数，那么答案应为下列两种情况较大者。

①：取第一个点，可取得最大价值为宝物[1,n-1]的最大价值。

②：不取第一个点，可取得最大价值为宝物[2,n]的最大价值。

动态规划，状态转移方程：\(dp[i] = max(dp[i-1], dp[i - 2] + V[i])\)

分析

时间复杂度：\(O(n)\)。

参考代码

//

// Created by AlvinZH on 2017/12/4.

// Copyright (c) AlvinZH. All rights reserved.

//

#include <cstdio>

#include <iostream>

#define max(a, b) a > b ? a : b

using namespace std;

int n;

int V[100005];

/*

int dp[100005];

int maxValue(int left, int right)

{

    dp[left] = V[left];

    dp[left+1] = max(V[left], V[left+1]);

    for(int i = left+2; i <= right; i++)

        dp[i] = max(dp[i-1], dp[i - 2] + V[i]);

    return dp[right];

}

*/

//优化代码

int maxValue(int left, int right)

{

    int LastTwo = 0, LastOne = 0;

    for(int i = left; i <= right; i++)

    {

        int temp = LastOne;

        LastOne = max(LastOne, LastTwo + V[i]);

        LastTwo = temp;

    }

    return LastOne;

}

int main()

{

    while(~scanf("%d", &n))

    {

        for(int i = 1; i <= n; i++)

            scanf("%d", &V[i]);

        if(n == 1) printf("%d\n", V[1]);

        else printf("%d\n", max(maxValue(1, n-1), maxValue(2, n)));

    }

}

巴特西

2016级算法期末模拟练习赛-B.AlvinZH的青春记忆I

1083 AlvinZH的青春记忆I

思路

分析

参考代码

最新文章

热门文章