HDU 1500 - Chopsticks
Problem : The similar with 1421:Ban Qin SHi. The difference is that each set has 3 elements, only the smaller 2 elements are considered into the calculation.
Solution : Denotes f[i][j], to choose i chopsticks start from the j-th chopsticks and the minimum total badness. Thus f[i][j]=min(f[i][j+1](if start from j+1-th chopsticks remains no less than 3i chopsticks), f[i-1][j+2]+SQR(a[j]-a[j+1]);(It's no need to check whether there are 3i-3 chopsticks start from j-2, since 3i chopstics exists start from j. In addition, the remaining chopsticks which is not in previous sets can always be the largest one of the i-th set. [])).
Difficulty : Only the anti oritation can get answer in O(N^2) time. Since it's monotone property.
Stretch : How to do if choose the largest 2 chopsticks to calculate badness, or the largest and smallest one.