HDOJ 5586-Sum【经典DP】

àì夳堔傛蜴生んèń 2022-08-21 08:57 141阅读 0赞

# Sum #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)**

Total Submission(s): 1318 Accepted Submission(s): 664

Problem Description

There is a number sequence  A![Image 1][]1![Image 1][],A![Image 1][]2![Image 1][]....A![Image 1][]n![Image 1][]![Image 1][],you can select a interval \[l,r\] or not,all the numbers  A![Image 1][]i![Image 1][](l≤i≤r)![Image 1][] will become  f(A![Image 1][]i![Image 1][])![Image 1][].  f(x)=(1890x\+143)mod10007![Image 1][].After that,the sum of n numbers should be as much as possible.What is the maximum sum?

Input

There are multiple test cases.  
First line of each case contains a single integer n.  (1≤n≤10![Image 1][]5![Image 1][])![Image 1][]  
Next line contains n integers  A![Image 1][]1![Image 1][],A![Image 1][]2![Image 1][]....A![Image 1][]n![Image 1][]![Image 1][].  (0≤A![Image 1][]i![Image 1][]≤10![Image 1][]4![Image 1][])![Image 1][]  
It's guaranteed that  ∑n≤10![Image 1][]6![Image 1][]![Image 1][].

Output

For each test case,output the answer in a line.

Sample Input

2
    10000 9999
    5
    1 9999 1 9999 1

Sample Output

19999
    22033

解题思路：

主要考虑通过那个算式计算后会不会减少，就是取模会减少这种情况，不然就是普通dp，我们只需要，将每个计算后的数减去这个数的原值，这样在判断时就会只需要判断是否大于零。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define ll long long
    using namespace std;
    int n;
    ll num[100100];
    ll dp[100100];
    ll f(ll a){
    	return (1890* a +143)% 10007;	
    }
    int main()
    {
    	while(scanf("%d",&n)!=EOF)
    	{
    		int i,j;
    		ll sum=0;
    		for(i=1;i<=n;i++)
    		{
    			scanf("%lld",&num[i]);
    			sum+=num[i];
    		}
    		for(i=1;i<=n;i++)
    		{
    			num[i]=f(num[i])-num[i];//变成判断是否大于零的普通DP 
    		}
    		memset(dp,0,sizeof(dp));
    		ll ans=0;
    		for(i=1;i<=n;i++)
    		{
    			dp[i]=dp[i-1]>0?dp[i]+dp[i-1]+num[i]:num[i]+dp[i];
    			ans=max(dp[i],ans);
    		}
    		printf("%lld\n",ans+sum);
    	}	
    	return 0;
    }

[Image 1]: