Re: [ACM ] 11077 WA

看板C_and_CPP (C/C++)作者bleed1979 (十三)時間16年前 (2010/03/03 22:22)推噓2(2推 0噓 3→)

留言5則, 3人參與討論串2/2 (看更多)

先來個4 x 4 array好了。 1. 首先，K = 0一定是1 0 0 1 2 3 4 1 1 2 1 3 1 4 1 2. K >= N一定是0 0 0 1 2 3 4 1 1 0 0 0 0 2 1 0 0 0 3 1 0 0 4 1 0 3. N = 2, K = 1 是 1 0 0 1 2 3 4 1 1 0 0 0 0 2 1 1 0 0 0 3 1 0 0 4 1 0 4. N = 3, K = 1 是 3 0 0 1 2 3 4 1 1 0 0 0 0 2 1 1 0 0 0 3 1 3 0 0 4 1 0 5. N = 3, K = 2 是 2 0 0 1 2 3 4 1 1 0 0 0 0 2 1 1 0 0 0 3 1 3 2 0 0 4 1 0 6. 我們來分析N = 4, K = 2 1 2 3 4 swap 1 4可以和1換，可以和2換，可以和3換，所以有3個可能 swap2 假設4和3換, swap剩1次 1 2 4 3 看前三個1 2 4，是不是變成N = 3, K = 1了所以是3 * (N = 3, k = 1) 現在討論1 2 3 4的3 swap1 3可以和2換，可以和1換，所以有2個可能 swap2 假設3和2換，swap剩1次 1 3 2 4 看前面的1 3，是不是變成N = 2, K = 1了所以是2 * (N = 2, K = 1) 同理2和1類推以上所有都要加起來才是N = 4, K = 2的解所以一個N x N array 最內圈的寫法 for (k = i - 1; k != 0; --k) A[i][j] += k * A[k][j - 1]; 外面兩圈當然是i和j的遞增也就是說，這題速解為Dynamic Programming 所以先作precalculation，while讀入測資後直接輸出Array值 C++速度大約是0.012s, C應該可以更快 Bleed ※ 引述《adks3489 (Double C)》之銘言： : 題號：11077 : 題目網址：http://acm.uva.es/p/v110/11077.html : 遇到的問題：就..WA : 有問題的code： http://codepad.org/fWDqxTjH : 補充說明： : 大概講一下這題目的內容， : Input為N及K : N是有數列長度,K是作排序的次數 : Output的要求為找出長度為N，需要K個swap來做排序的數列共有多少個 : 範例： : N=3 數列| swap次數 : 1 2 3 | 0 : 1 3 2 | 1 : 2 1 3 | 1 : 2 3 1 | 2 : 3 1 2 | 2 : 3 2 1 | 1 : N K Output : 3 0 | 1 : 3 1 | 3 : 3 2 | 2 : 送出去給了我WA，我也不知道該怎麼辦了 : 救救我吧 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.32.177.97