發表新討論
#24184: 也許是個好方法


yuki71701@gmail.com (Nöžõmi希)

e417. 乘法~乘法~加法~ -- π | From: [1.175.22.43] | 發表日期: 2021-01-26 00:21

假設題目是 1 2 3 4 5

暴力解就是       1*2 + 1*3 + 1*4 + 1*5 + 2*3 + 2*4 + 2*5 + 3*4 + 3*5 + 4*5

稍微改一下排序 1*2 + 1*3 + 2*3 + 1*4 + 2*4 + 3*4 + 1*5 + 2*5 + 3*5 + 4*5

就能寫成          1*2 + (1+2)*3 + (1+2+3)*4 + (1+2+3+4)*5

這樣雖然還是有點暴力，不過時間複雜度大概就會降到O(n)了

#33982: Re: 也許是個好方法


wrr606@gmail.com (Function)

e417. 乘法~乘法~加法~ -- π | From: [223.139.197.79] | 發表日期: 2023-02-21 14:42

假設題目是 1 2 3 4 5

暴力解就是       1*2 + 1*3 + 1*4 + 1*5 + 2*3 + 2*4 + 2*5 + 3*4 + 3*5 + 4*5

稍微改一下排序 1*2 + 1*3 + 2*3 + 1*4 + 2*4 + 3*4 + 1*5 + 2*5 + 3*5 + 4*5

就能寫成          1*2 + (1+2)*3 + (1+2+3)*4 + (1+2+3+4)*5

這樣雖然還是有點暴力，不過時間複雜度大概就會降到O(n)了

太神啦，感謝，AC了

AC (1.2s, 7.8MB)
ZeroJudge Forum