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


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

學校 : 不指定學校
編號 : 128773
來源 : [223.139.111.73]
最後登入時間 ：
2024-04-09 22:18:52
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)

學校 : 國立金門大學
編號 : 133433
來源 : [1.174.41.11]
最後登入時間 ：
2024-04-16 21:49:19
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