Problem
F - Changing Digits
[Description]
给出2个整数n（n<10^100）和k（k<10000），求满足以下条件的整数m
1、m与n位数相同
2、m能被k整除
3、满足以上两点时，m和n在相同位置的地方，数字不同的个数最少
4、满足以上三点时，m值最小
[Intput]
输入包含多组测试数据，每组数据占一行两个数，n，k (n > k)，均不含前导0。
[Output]
对于每组数据输出一个适合的m
[Sample Input]
2
2
619103
3219
[Sample Onput]
2
119103
这道题是考试的时候遇到的，最后一道，F题，分析了一下，没什么思路，就用记忆化搜索试了试，结果越写越有感觉，就觉得记忆化搜索是正解，然后。。。就A了。
大致过程是这样的：n的第i位(从0开始计数)取j时模上k的值我们都可以预处理出来存在f[i][j]中，如：23333，其中第2位为3，若k=9，则f[2][3]=300%9=3。那么我们就可以得到n%k的值，记为reet。设n的第i位为num[i]，则将num[i]改为j后新的数模上k的值ret为:
ret=(n-f[i][num[i]]+f[i][j])%k=(reet-f[i][num[i]]+f[i][j]+k)%k
加k是因为可能为负值。则将n的某一位改变之后新的数模上k的余数我们都可以计算出来，基于此，我们就可以设计状态了：
设n的长度为l。
用bool dfs(int u,int remain)记录能否通过修改u到l这些位置上的数使得新得到的数模上k等于0。如果能够，返回真，同时记录下最少修改的n的位数与在这种情况下第u位的值。
由于题目要求在修改n的位数最少时，使得m尽量小。所以我们在枚举u这一位放什么数字的时候从小到大枚举，这样我们就只需根据长度来更新就可以了，因为按照这样的顺序得到的第一个长度为len的情况m一定是最小的。最后再输出就行了。
我的代码虽然长了点，但写的结构还是蛮清楚的，也有很多注释，代码如下：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
/*
(a-b)%k=((a%k-b%k)+k)%k
*/
int k,l,reet;
char ss[100+10];
int num[100+10],f[100+10][10+10],vis[100+10][10000+10],dp[100+10][10000+10],len[100+10][10000+10];
//num[i]:n的第i位上的数(n是从高位到低位存的)
//f[u][i]:n的第u位取i时的余数
//vis[u][remain]:标记当前状态是否到达过。
//dp[u][remain]: 当前状态的最优解时第u位的取值。
//len[u][remain]:当前状态的最优长度
bool dfs(int u,int remain)//在剩下的u位中，余数为remain,能否达到。
{
if(u==l)return false;//搜到第l位仍然没有将余数消为0，返回不能到达
if(vis[u][remain]!=-1)return vis[u][remain];//标记都懂得
//先考虑达到remain的最小改变位数，再考虑最小
int ret;
//初始化
len[u][remain]=l+2;
dp[u][remain]=num[u];
int ok=0,pi;
//搜索顺序由小到大，保证一旦更新答案，即为当前长度的最优解
for(int i=0;i<=9;i++)
{
if(u==0&&i==0)continue;//第一位不能取0
if(i!=num[u])pi=1;//标记是否改变当前的数
else pi=0;
ret=remain-f[u][num[u]]+f[u][i];//计算
while(ret<0)ret+=k;//计算改变后余数
ret%=k;
if(ret==0)//目标，更新
{
if(1<len[u][remain])//更新只看长度
{
len[u][remain]=1;
dp[u][remain]=i;
ok=1;//标记有解
}
}
else if(dfs(u+1,ret))//能到达目标,更新
{
if(len[u+1][ret]+pi<len[u][remain])//更新只看长度
{
len[u][remain]=len[u+1][ret]+pi;
dp[u][remain]=i;
ok=1;//标记有解
}
}
}
if(ok)//有解，返回真
{
//printf("len[%d][%d]=%d dp[%d][%d]=%d\n",u,remain,len[u][remain],u,remain,dp[u][remain]);
return vis[u][remain]=true;
}
return vis[u][remain]=false;//返回假
}
void init()
{
memset(vis,-1,sizeof(vis));
l=strlen(ss);
for(int i=0;i<l;i++)//处理每一位的数字
{
num[i]=ss[i]-'0';
}
for(int i=l-1;i>=0;i--)//递推第i位为j时%k的值
{
f[i][0]=0;
if(i<l-1)f[i][1]=(f[i+1][5]+f[i+1][5])%k;//不是个位，用小一位的数更新
else f[i][1]=1%k;//是个位，用1更新
for(int j=2;j<=9;j++)
f[i][j]=(f[i][j-1]+f[i][1])%k;
}
reet=0;//计算余数
for(int i=0;i<l;i++)
{
reet=(reet+f[i][num[i]])%k;
}
}
void print(int u,int remain)
{
if(remain==0)//已经到达状态，接下的原样输出
{for(int i=u;i<l;i++)printf("%d",num[i]);printf("\n");return;}
else printf("%d",dp[u][remain]);
if(u==l-1)//边界，返回
{
printf("\n");
return;
}
int ret=remain-f[u][num[u]]+f[u][dp[u][remain]];
while(ret<0)ret+=k;
ret%=k;//计算余数，继续输出
print(u+1,ret);
}
int main()
{
while(scanf("%s%d",ss,&k)==2)
{
init();//预处理每一位为(0-9)这些数时的余数
if(reet==0)//n%k==0,最优解就是n
{
printf("%s\n",ss);
continue;
}
if(l==1)//长度为1,n%k!=0,0为最优解
{
printf("0\n");
continue;
}
dfs(0,reet);//搜索
print(0,reet);//输出
}
return 0;
}
考完以后也去搜了下题解，有直接DP的，但本人奇弱，无法确定DP的顺序，只好写了记忆化搜索，个人感觉简便许多，代码的可读性更强，debug也要容易一点。
还有大牛写深搜+强剪枝，居然也A了，看到那些神一般的剪枝与定理，只有膜拜之。
这道题就这样了，只要想到了还是蛮好写的。