hdu 5586(最大连续子序列和)

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

官方题解：

令A i =f(A i )−A i  ,然后求一遍最大连续子序列和就能知道最多能增加的值。  

PS:感觉这题好巧妙啊。。很难想到去利用最大连续子序列和求增量。。

#include <iostream> #include <cstdio> #include <cstring> using namespace std;typedef long long LL; const int maxn = 1e5+5; const int mod = 1e4+7; int arr[maxn], data[maxn];int main() {int n;while(~scanf("%d",&n)){LL sum = 0;for(int i=0; i<n; i++){scanf("%d",&arr[i]);sum += arr[i];data[i] = ((arr[i]*1890+143)%mod) - arr[i];}LL Max = 0, tmp = 0;for(int i = 0; i < n; i++){tmp += data[i];if(tmp > Max)Max = tmp;if(tmp < 0)tmp = 0;}LL ret = sum + Max;printf("%I64d\n",ret);}return 0; }

总结

以上是生活随笔为你收集整理的hdu 5586(最大连续子序列和)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。