Description:

Give you a sequence of integer numbers which are 1 or 0. You are to find the number of consecutive sub-sequence, which the xor value between all these numbers has the maximum value. The first number of the sequence is 1 and the last is 1. There are (n+1) 1’s in the sequence. N numbers will be given. The i-th number is the index of (i+1)-th 1 minus the index of i-th 1. For example: if the sequence is 1010100010001, 4 2 2 4 4 will be given.

 

Input:

There are multiple cases. For each case: Line 1: A single integer N (1<=N<=20000). Followed N integers ranging from 1 to 20000.

Output:

For each case output the result in a single line.

Sample Input:

4
2 2 4 4
5
3 1 2 4 5

Sample Output:

49
70

Hint:

1.1 ^ 1 = 0, 1 ^ 0 = 1, 0 ^ 1 = 1, 0 ^ 0 = 0. 2.In the example, sub-sequence 10 has the maximum value ‘cause 1 xor 0 = 1;the same as 10101, 1010100010001, and so on.

算不上DP的DP......就是處理01串的奇偶性.....

DP[i][j]表示第i個1，j有6種情況。
dp[i][0] = dp[i - 1][1] 表示偶數(shù)個1，且最后一個1在末尾。
dp[i][1] = dp[i - 1][0] + dis 表示奇數(shù)個1，且最后一個1在末尾。
dp[i][2] = f[i - 1][2] + f[i - 1][0] 表示偶數(shù)個1，且最后一個1不在末尾。
dp[i][3] = f[i  - 1][3] + f[i - 1][1] 表示偶數(shù)個1，且最后一個1不在末尾。
dp[i][4] = f[i - 1][4] + (dis - 1) * f[i - 1][0] 表示偶數(shù)個1，且最后一個是0不在末尾。
dp[i][5] = f[i - 1][5] + (dis - 1) * f[i - 1][0] 表示偶數(shù)個1，且最后一個是0不在末尾。
上面六個關(guān)系式列舉了所以情況，但是只用到了(dp[i][0], dp[i][1], dp[i][3], dp[i][5])四個式子。

友情提示，ans是超過int的，用long long吧，我因為這個吃了三次WA.....

代碼：