|
|
вернуться в форумHello! Can somebody tell me if there is a faster algo than O(Q^2*N)? My algo works pretty fast, but I wondered if there is a better way to do it. My solution Q*N, lol Or no I'm not sure Edited by author 11.03.2016 21:50 Edited by author 11.03.2016 21:50 My algo is fills dp[vertex][presaved edges] array (result is dp[1][Q]), where total loops N^3/6 < 2*10^5. There maximum presaved edges = Q, but more vertexes have less edges than Q. Let edges[v] - number of edges of v vertex. So there O( N * sum( edges[ v ] * ( edges[ v ] + 1 ) / 2 ) ) = O( N^3 / 6 ). |
|
|