PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] ICPC 6015

看板Prob_Solve (計算數學 Problem Solving)作者seanwu (sean)時間11年前 (2013/03/17 18:25)推噓6(6推 0噓 21→)

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

※ 引述《lubrige (lubrige)》之銘言： : 題目: http://ppt.cc/Aogu : 給予整數 N, R, Q，求一最大的正整數 M，使得 : (1) 將 N 和 M 寫成十進位表示時，M 是 N 的 subsequence : (2) M 除 Q 會餘 R : 其中 1 <= N < 10^1000, 0 <= R < Q <= 1000 : 目前的做法是 : 定義狀態 f[i][j]，表示從 N 的最高位開始，考慮過前 i 個數字是否選進 M，且 : 餘 j 的情況時 M 的最大長度 (暫不考慮 value 大小)，其中若為走不到的狀態則填-1 : 轉移為 (d(k) 為 k 從最高位下來第 k 個數字， zero base) : / f[i - 1][j] : f[i][j] = max | : \ f[i - 1][j'] + 1, j = (10 * j' + d(i - 1)) % Q, : if f[i - 1][j'] != 0 or d(i - 1) != 0 : boundary condition: : 1. f[0][0] = 0 : 2. f[0][i] = -1, for 0 < i < Q 上面長度 f[i][j] 的計算是正確的，沒有問題 : 最大長度的表填完之後，再從 N 的最低位做回來，並且另外開一張表 g[i][j]， : 記到 f[i][j] 這格所形成的最長 subsequence，最高位數字是多少。有點看不太懂 "f[i][j] 這格所形成的最長 subsequence" 是指哪一段 sequence 根據你的遞迴式，腦補 g[i][j] 的意思是(?): 選擇 M 的第 f[i][j] 個數字 (zero base) 最大可行值是 g[i][j] 並且，這個值是從 d[i-1]~d[n-1] 選來的，且 M 的前 i-1 個位模 Q 的餘數是 j : 對於不是 -1 的格子，取下面裏比較大的數字 (這部份用 buttom up 來說)： : 1. g[i + 1][j], if f[i + 1][j] == f[i][j] : 2. d(i), if f[i + 1][j'] == f[i][j] + 1, j' = (10 * j + d(i)) % Q 在算出 g[i][j] 後，應該是要再從高位找下來? 那這邊的找法，應該是從 i=j=0 開始，如果 g[i][j] 這格是 case 1. 就 i++; 看下一格就好如果是 case 2.，輸出 g[i][j]; j=(j*10+g[i][j])%Q; i++; 不知道原 po 的做法是不是這樣? 如果是的話就要先判 case 2. 因為數字一樣時先取走一定比較好，反過來雖然之後還是能拿到一樣的數字但可能會導至之後可以選的數字變小例如 881 4 7 這個測資，算出 f[][], g[][] 應該是這樣 f 0 1 2 3 4 5 6 0 0 * * * * * * 1 0 1 * * * * * 2 * 1 * * 2 * * 3 * * * * 2 * * g 0 1 2 3 4 5 6 0 8 * * * * * * 1 8 8 * * * * * 2 * 1 * * X * * g[0][0] 的 8 是來自 g[1][0] 或 d[0] (f[1][8%7]==f[0][0]+1, case 2.) 都行不過這裡要選 case 2. (i,j)=(0,0)=>(1,1)=>(2,4)=>(3,4) 8 8 X 選 case 1. 的話， (i,j)=(0,0)=>(1,0)=>(2,1)=>(3,4) X 8 1 : 另外因為這部份倒過來做，所以為了避免抓到不是從 f[length(N)][R] 填回來的數字， : 上面的計算還考慮是不是從 f[length(N)][R] 填回來的，如果不是的話一樣不考慮 : g[i + 1][j] 或 d(i)，這部份再記一張來解決。 : 不過答案不對，想請問一下有沒有什麼沒有考慮到地方，先謝謝大家 0w0/ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.4.194 ※ 編輯: seanwu 來自: 140.112.4.194 (03/17 18:26)

推