HU-586 Sum（DP）

2486 ワード

http://acm.hdu.edu.cn/showproblem.php?pid=5586
Sum
Time Limit：2000/1000 MS（Java/Others）メモリLimit：65536/65536 K（Java/Others）
Problem Description
The re is a number sequence
A 1,A 2….An，you can select a interval[l，r]or not，all the numbers
Ai（l≦i≦r） will become
f(Ai)
f(x)=(1890 x+143)mod 1007.After that，the sum of n numbers shound be as much possible.What is the maximm sum？

Input
The re are multiple test cases.
First line of each case contains a single integer n.
（1≦n≦105）
Next LINE contains n integers
A 1,A 2….An.
（0≦Ai≦104）
It's garanted that
Σn≦106.

Output
For each test case，output the answer in a line.

Sample Input


   
   
   
   
    
    
    
    2
10000 9999
5
1 9999 1 9999 1

Sample Output

タイトル：n個の数A 1，A 2…A nをあげて、区間を選択してもいいです。区間の中で、各数xはf（x）になります。その中でf（x）=（1890＊x＋143）mod 10007。最後のn個の数と最大可能性はどれぐらいですか？
公式DPの方法とは違って、自分のDPの方が早いような気がします。
公式方法：令a[i]=f(a[i])-a[i]を求め、最大連続サブシーケンスと最大増加できる値を知ることができる。
個人の考え方:
DPはまだよくないです。考える時間は長いです。
いろいろ考えた末、dp[i][j]（j=0,1,2）で現在の状態を表すことができると思いました。
dp[i][0]は現在置換区間に入っていないことを示しています。dp[i-1][0]から移動するしかないです。
dp[i][1]は現在置換区間にあり、dp[i-1][0]とdp[i-1][1]から移行することができます。
dp[i][2]は現在置換区間から離れていることを示し、dp[i-1][1]とdp[i-1][2]によって移動することができます。
状態移行方程式は以下の通りです。
dp[i][0]=dp[i-1][0]+a[i]
dp[i][1]=max（dp[i-1][0]，dp[i-1]、[1]）+f（a[i]）;
dp[i]、[2]=max（dp[i-1][1]，dp[i-1]、[2]）+a[i]

#include <cstdio>
#include <algorithm>

using namespace std;

int n,num,i,dp[2][3];//dp[i&1][0]            ，dp[i&1][0]          ，dp[i&1][2]          

inline int f() {
    return (1890*num+143)%10007;
}

int main() {
	while(1==scanf("%d",&n)) {
        dp[0][0]=dp[0][1]=dp[0][2]=0;
        for(i=1;i<=n;++i) {
            scanf("%d",&num);
            dp[i&1][0]=dp[(i-1)&1][0]+num;
            dp[i&1][1]=max(dp[(i-1)&1][0],dp[(i-1)&1][1])+f();
            dp[i&1][2]=max(dp[(i-1)&1][1],dp[(i-1)&1][2])+num;
        }
        printf("%d
",max(dp[n&1][0],max(dp[n&1][1],dp[n&1][2])));
	}
	return 0;
}

GavaではTreeRangeMapが基本的に使用されています。

Ajaxバックグラウンドの呼び出し方法