ACM学习历程—HDU5586 Sum（动态规划）(BestCoder Round #64 (div.2) 1002)

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

题目大意就是把一段序列里面的数替换成f(x)，然后让总和最大。

首先可以计算出初始的总和，以及每一个值换成f(x)的增益a[x]。

那么就是求一段子序列a[x]的最值了，经典的DP。

其实我一开始想到这个思路是因为列了一个式子：

S = sum(n)-sum(rt)+sum’(rt)-sum’(lt)+sum(lt)

=sum(n)+(sum’(rt)-sum’(lt))-(sum(rt)-sum(lt))

于是发现了就是求lt到rt差值和的最值。

最后答案加上初始的总和输出。

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <set>

#include <map>

#include <queue>

#include <string>

#define LL long long

using namespace std;

const int maxN = ;

int n, a[maxN];

LL s;

void input()

{

    s = ;

    int k;

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

    {

        scanf("%d", &k);

        s += k;

        a[i] = (*k+)%-k;

    }

}

void work()

{

    LL ans = , now = ;

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

    {

        if (now >= ) now += a[i];

        else now = a[i];

        ans = max(ans, now);

    }

    cout << ans+s << endl;

}

int main()

{

    //freopen("test.in", "r", stdin);

    while (scanf("%d", &n) != EOF)

    {

        input();

        work();

    }

    return ;

}

巴特西

ACM学习历程—HDU5586 Sum（动态规划）(BestCoder Round #64 (div.2) 1002)

最新文章

热门文章