Solve #349 B Div 1 with five cities!

Правка en3, от M_H_M, 2016-05-04 15:07:54

Round 349 B Div1 : 666B - World Tour.
The Idea of problem is fixing two middle cities!
But I solved the problem by this Idea :
Consider that the answer's cities are a, b, c, d and a < b < c < d
---- dp[ k ][ i ] = the maximum length with k cities so that k'th city is i(labels are increasing!).
---- We can update dp with O(n ^ 2) [ dp[ k ][ i ] = max(j < i : dp[ k — 1 ][ j ] + d[ j ][ i ]) ]

We shuffle the labels of cities while the labels of answer's cities become increasing!
The mathematical expectation of the above algorithm is (4! * 4 * N ^ 2) :))
My implementation : 17588529.
We can have a harder problem with five cities : (5! * 5 * N ^ 2)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский M_H_M 2016-05-04 15:07:54 1 Tiny change: ':17588529] . <br> \nW' -> ':17588529]. <br> \nW'
en2 Английский M_H_M 2016-05-04 09:31:34 1
en1 Английский M_H_M 2016-05-02 17:41:56 762 Initial revision (published)