其实这道题只告诉了一个事
当出现多个满足答案约束条件是，我们可以求一个再求一个，不要一下子全求完
前两个条件怎么弄之前已经做过类似的了
于是我们可以用记忆化搜索找出最小差异
然后配合最小差异来剪枝，搜索出最小答案
1 var a,b:array[0..110] of longint; 2 f:array[0..110,0..10010] of longint; 3 n,m,k,i:longint; 4 can:boolean; 5 s:string; 6 7 function min(a,b:longint):longint; 8 begin 9 if a>b then exit(b) else exit(a); 10 end; 11 12 function differ(j,cur:longint):longint; //f[j,cur]表示处理到第j位前面余数为cur的情况最小差异数 13 var i,wh,s:longint; 14 begin 15 if (j=n+1) then 16 begin 17 if cur=0 then exit(0) 18 else exit(1000); 19 end; 20 if f[j,cur]<>-1 then exit(f[j,cur]); 21 if j<>1 then s:=0 else s:=1; 22 f[j,cur]:=1000; 23 for i:=s to 9 do 24 begin 25 wh:=differ(j+1,(cur*10+i) mod m); 26 if i<>a[j] then inc(wh); 27 f[j,cur]:=min(f[j,cur],wh); 28 end; 29 exit(f[j,cur]); 30 end; 31 32 procedure dfs(j,wh,cur:longint); 33 var i,s:longint; 34 begin 35 if (j=n+1) then 36 begin 37 if cur=0 then can:=true; 38 exit; 39 end; 40 if can then exit; 41 if f[j,cur]+wh>k then exit; //剪枝 42 if j<>1 then s:=0 else s:=1; 43 for i:=s to 9 do 44 begin 45 b[j]:=i; 46 if (i=a[j]) then 47 dfs(j+1,wh,(cur*10+i) mod m) 48 else 49 dfs(j+1,wh+1,(cur*10+i) mod m); 50 if can then exit; 51 end; 52 end; 53 54 begin 55 while not eof do 56 begin 57 readln(s); 58 n:=length(s); 59 for i:=1 to n do 60 a[i]:=ord(s[i])-48; 61 readln(m); 62 if s='0' then 63 begin 64 writeln(0); 65 continue; 66 end; 67 fillchar(f,sizeof(f),255); 68 k:=differ(1,0); 69 // writeln(k); 70 can:=false; 71 dfs(1,0,0); 72 for i:=1 to n do 73 write(b[i]); 74 writeln; 75 end; 76 end.