※ 引述《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)