题目链接：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 = 100004; int n, a[maxN]; LL s; void input() { s = 0; int k; for (int i = 0; i < n; ++i) { scanf("%d", &k); s += k; a[i] = (1890*k+143)%10007-k; } } void work() { LL ans = 0, now = 0; for (int i = 0; i < n; ++i) { if (now >= 0) 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 0; }
ACM学习历程—HDU5586 Sum（动态规划）(BestCoder Round #64 (div.2) 1002)
原文：http://www.cnblogs.com/andyqsmart/p/5003528.html
