题意：
给出2个整数N和K，求满足以下条件的整数M
1、M与N位数相同
2、M能被K整除
满足以上两点的情况下，与N不同位数的个数以及M值最小的优先
n<10^100
k<10000
解法：
考虑到k不大，状态可以设置为dp[i][k]，即i位的数字中余数为k的需要修改的最小值
但是由于最后一个约束条件，即数小的优先，如果从正向DP，不能满足要求
应为从状态i-1转移到状态i的过程中，贪心的DP保证了第i位取值最小。可能出现这种状况：
假设abcd%k==efgh%k
d<h,但a>e。这样就不满足题意了。
解决方法是逆向DP，这样既能保证靠近前面的位取值最小。
代码：
1
Source Code
2
3Problem: 3373 User: yzhw
4Memory: 12180K Time: 1235MS
5Language: G++ Result: Accepted
6
7Source Code
8# include <cstdio>
9# include <cstring>
10using namespace std;
11int dp[105][10000];
12int path[105][10000][2];
13void print(int start,int left,int len)
14
{
15
if(start>=len+1) return;
16 printf("%d",path[start][left][1]);
17 print(start+1,path[start][left][0],len);
18
}
19int main()
20{
21 char str[105];
22 int mod[105];
23 while(scanf("%s",str+1)!=EOF)
24
{
25 int k;
26 scanf("%d",&k);
27 memset(dp,-1,sizeof(dp));
28 mod[strlen(str+1)]=1%k;
29 for(int i=strlen(str+1)-1;i>=1;i--)
30 mod[i]=(mod[i+1]*10)%k;
31 dp[strlen(str+1)+1][0]=0;
32 for(int i=strlen(str+1);i>0;i--)
33 for(int p=(i==1?1:0);p<10;p++)
34 for(int j=0;j<k;j++)
35 if(dp[i+1][j]!=-1)
36 if(dp[i][(j+p*mod[i])%k]==-1||dp[i][(j+p*mod[i])%k]>dp[i+1][j]+(p!=str[i]-48))
37 {
38 dp[i][(j+p*mod[i])%k]=dp[i+1][j]+(p!=str[i]-48);
39 path[i][(j+p*mod[i])%k][0]=j;
40 path[i][(j+p*mod[i])%k][1]=p;
41
}
42 print(1,0,strlen(str+1));
43 printf("\n");
44 }
45 return 0;
46}
47
48
49