【郑轻】[1837]LT说我不服

问题描述

LT说我不服

时间限制：1 Sec内存限制：128 MB

Description

对于上一道题目LT不服，表示那么简单的题目不屑于去做，所以我们决定加大一下题目的难度，下面是我们LT出的题目：假如给你一个由n个数组成的序列A1, A2, A3, A4 …… An。你可以选择任意一个大小的区间，将其中的每一个数x变成(x*1888+101)%14507。求这n个数的最大和可能是多少。

Input

输入有多组数据每组数据第一行输入一个整数n为序列元素个数。(1 <= n <= 100000) 第二行n个整数A1, A2, A3, A4 …… An。(0 <= Ai <= 10000)

Output

每组样例输出一行答案。

Sample Input

  2
10000 9999
5
1 9999 1 9999 1

Sample Output

  19999
21989

HINT

范围在int内

问题分析

这一题可以转化为求最大子串和问题

因为若不改变值，则结果为a1~n的和

若求出每一个数的(x*1888+101)%14507与x的差值

改变某一区间的值，则可以表示为选取一个子串

若想要最终结果最大，很显然要让选取的这个子串和最大

所以dp求解，复杂度O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
int a[100200];
int main() {
	int n;
	while(scanf("%d",&n)!=EOF) {
		int sum=0,res=0,x=0;
		for(int i=0; i<n; i++) {
			scanf("%d",&a[i]);
			sum+=a[i];
			if(x>0) {
				x+=(a[i]*1888+101)%14507-a[i];
			} else
				x=(a[i]*1888+101)%14507-a[i];
			if(res<x)
				res=x;
		}
		printf("%d\n",sum+res);
	}
	return 0;
}

题目地址:【郑轻】[1837]LT说我不服