Scrambling around inside the question bank, I turned up.
Because the subsequence doesn't need to consider the order of the elements inside this question, the original sequence in whatever order doesn't affect the answer.
So first arrange the elements in order from largest to smallest and then consider the contribution of each element.
In the current sequence, for the element\(a_i\), it may be worthwhile to set it as the minimum value and to find which sequences it can serve as the minimum value. It is easy to find that it can only be used as a minimum when compared to\(1\sim i\) The elements in the produce a contribution.
Specifically, for the current transition from\(1\sim i\) medium\(a_j\)and if it is maximized, then by\(a_i\) cap (a poem)\(a_j\) Both of these values as the most-valued sequence element must be in the\(j\sim i\) between them, and students who have studied sets know that such a sequence obviously has\(2^{i-j-1}\) Individuals.
This gives us a\(\mathcal{O}(n^2)\) The solution to the problem is as follows:
due to\(i-j-1\) There will be negative numbers in it, which we can get by changing the equation slightly:
But this is obviously not enough, so we can
right\(j\) The enumeration is optimized. Easy to think of preprocessing.
We use an intermediate variable\(sum\) denotes the value inside the second parenthesis. After each computed answer, we let\(sum\gets sum\times 2+a_i\) Ready to go.
Remember to take the mold.
Submission of records