作者lubrige (lubrige)
看板Prob_Solve
標題[問題] ICPC 6015
時間Sat Mar 16 18:16:51 2013
題目:
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
最大長度的表填完之後，再從 N 的最低位做回來，並且另外開一張表 g[i][j]，
記到 f[i][j] 這格所形成的最長 subsequence，最高位數字是多少。
對於不是 -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
另外因為這部份倒過來做，所以為了避免抓到不是從 f[length(N)][R] 填回來的數字，
上面的計算還考慮是不是從 f[length(N)][R] 填回來的，如果不是的話一樣不考慮
g[i + 1][j] 或 d(i)，這部份再記一張來解決。
不過答案不對，想請問一下有沒有什麼沒有考慮到地方，先謝謝大家 0w0/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.215.18
※ 編輯: lubrige 來自: 118.168.215.18 (03/16 18:18)
1F：推 seanwu:我照你的做法AC了，注意填 g[i][j] 時，如果兩個case都可以 03/17 17:16
2F：→ seanwu:要選 2.，意思是一樣的數字選高位的優先 03/17 17:17
3F：→ seanwu:可能會錯的測資: 881 4 7，答案是 88，選錯會變成 81 03/17 17:18
4F：推 bleed1979:請問有沒有刁鑽的測資啊，一直WA。 03/23 17:32