題意:
(from luckycat)
解法:
因為 n 最大到 50，所以暴力計算是沒辦法的喔。
所以要利用 DP 來解，舉個例子，如果一個方程式的根是 a、b、c 的話，
方程式則為 (x-a)(x-b)(x-c) = 0，展開得 x^3 - (a+b+c) x^2 + (ab+bc+ca) x - abc = 0，
我們定義 dp[ i ][ j ] 為 我們討論前 i 個根以第 i 個根為結尾且總共有 j 個數(包含 i )的乘法，則遞迴定義：
dp[ i ][ j ] =
{ num[ i ], if j = 1 & i > 0
{ sum( dp[ k ][ j - 1 ] * num[ i ], 1 <= k < i ), if j > 1 & i > 0
舉例：如上的假設 依序將 a、b、c 設為 1、2、3。
從一開始。
dp[ 1 ][ 1 ] = a
dp[ 2 ][ 1 ] = b
dp[ 2 ][ 2 ] = dp[ 1 ][ 1 ] * num[ 2 ] = a * b
dp[ 3 ][ 1 ] = c
dp[ 3 ][ 2 ] = dp[ 1 ][ 1 ] * num[ 3 ] + dp[ 2 ][ 1 ] * num[ 3 ] = a * c + b * c
dp[ 3 ][ 3 ] = dp[ 2 ][ 2 ] * num[ 3 ] = ( a * b ) * c
由這樣就可以得出
第一項 = 1
第二項 = dp[ 1 ][ 1 ] + dp[ 2 ][ 1 ] + dp[ 3 ][ 1 ]
第三項 = dp[ 2 ][ 2 ] + dp[ 3 ][ 2 ]
第四項 = dp[ 3 ][ 3 ]
TAG: Math, DP
注意:
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽