1837: LT說我不服

Time Limit: 1 Sec?? Memory Limit: 128 MB

Description

對于上一道題目LT不服，表示那么簡單的題目不屑于去做，所以我們決定加大一下題目的難度，下面是我們LT出的題目： 假如給你一個由n個數(shù)組成的序列A1, A2, A3, A4 …… An。你可以選擇任意一個大小的區(qū)間，將其中的每一個數(shù)x變成(x*1888+101)%14507。 求這n個數(shù)的最大和可能是多少。

Input

輸入有多組數(shù)據(jù) 每組數(shù)據(jù)第一行輸入一個整數(shù)n為序列元素個數(shù)。(1 <= n <= 100000) 第二行n個整數(shù)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內(nèi)

這一題可以轉(zhuǎn)化為求最大子串和問題

因為若不改變值，則結(jié)果為a_1~n的和

若求出每一個數(shù)的(x*1888+101)%14507與x的差值

改變某一區(qū)間的值，則可以表示為選取一個子串

若想要最終結(jié)果最大，很顯然要讓選取的這個子串和最大

所以dp求解，復雜度O(n)

#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];} elsex=(a[i]*1888+101)%14507-a[i];if(res<x)res=x;}printf("%d\n",sum+res);}return 0; }

題目地址:【鄭輕】[1837]LT說我不服

總結(jié)

以上是生活随笔為你收集整理的【郑轻】[1837]LT说我不服的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。