[7.21-26] code source - [sports festival] [Dan fishing war] [maximum weight division]

#668. Sports Festival

The question ： Given sequence , You need to rearrange the sequence , Make the sum of the prefix extreme value difference of the sequence minimum , Output this minimum value .$(n\le 2000)$

Answer key ：( Section dp) Code source daily question Div1 Sports Festival

Ideas ： Let's think about it , Now there is a good sequence , We insert an element that will become the extreme value of the sequence , So where does it contribute the least ？ Put it last . Because if you put it in the middle , It will affect the extreme value difference of the following prefix . For elements that do not become extreme values of the sequence , We don't consider the insertion strategy .

Then let's arrange the order , Expand outward from each point , The extension must be the extreme point . Definition $dp(i,j)$ As interval $[i,j]$ Minimum prefix extremum difference sum , Adopt outward expansion interval DP, $dp(i,j)=a_j-a_i+\max (dp(i+1,j),dp(i,j-1))$

Some intervals DP The topic （ Enumerate breakpoints , And interval merging ）： Section dp

AC Code ：http://oj.daimayuan.top/submission/299976

---

#702. Dan fishing war

The question ：$(n,q\le 5\times 10^5)$

Answer key ：( Monotonic stack / Tree array ) Code source daily question Div1 Dan fishing war

Ideas ： Because an element is good if and only if there is only one element in the stack after scanning . So let's simulate , Then the stack is processed and swept to each element , The subscript of the secondary element at the top of the stack . Now give us an interval , If we want an element to be good , Then we hope that this sub element is not in this interval , Then all the following elements will not appear , This element is good .

After preprocessing the sub element subscript of each element , The problem is transformed into an interval to find how many numbers are less than the given number , Classic offline tree array problem .

AC Code ：http://oj.daimayuan.top/submission/301595

---

#709. Maximum weight division

The question ： For a sequence , Define the weight of this sequence as the range of this sequence , That is, the difference between the maximum value and the minimum value of the sequence . Given a sequence $a$ , You can divide it into any continuous sequence , Find the maximum value of the weight sum of each segment .$(n\le 10^6)$

Answer key ：(DP) Code source daily question Div1 Maximum weight division

Ideas ： First of all, it is easy to think of dividing the sequence greedily into LIS and LDS Calculation , However, it's easy wa. We can DP, Definition $dp(i)$ Before presentation $i$ The maximum number of , However, it is found that the transfer is located in LIS or LDS Relevant , So open another dimension to distinguish . Definition $dp(i,j)$ Before presentation $i$ The maximum number of , And when $j=0/1$ Express $a_i$ In descent / Ascending sequence .

AC Code ：http://oj.daimayuan.top/submission/302950