HDU 5586 Sum (预处理 + 动态规划)

题目链接: 传送门 题意:给你n个数字，然后你可以对这n个数组的任意一个子区间进行一个操作，\(f(x)=(1890x+143)mod10007\)，或者不进行操作，问你怎样操作能使得加和最大 解题思路:我们通过预处理a数组元素，把改数字操作后的值和操作前的值进行一个做差存储在b数组里面，此时问题便转化为了求解b数组连续的子序列的和的值，当然如果b数组连续子序列和的值小于0，我们就不对a数组的元素进行任何操作，dp[i]表示的是长度为i的连续序列的最大值，动态转移方程为:\(dp[i] = max(dp[i-1],max_)\) Code:

#include
using namespace std;

const int INF = 0x3f3f3f3f, N  = 100005, mod = 10007;
int n,a[N],b[N],dp[N];

int main()
{
	while(~scanf("%d",&n)) {
		int sum  = 0;
		for(int i = 1; i