一開始写的高位往低位递推，发现这样有些时候保证不了第四条要求。于是又開始写高位往低位的记忆化搜索，又发现传參什么的蛋疼的要死。然后又发现高位開始的记忆化搜索就是从低位往高位的递推呀，遂过之。

dp[i][j]记录在i位 且 余数为j时的最优解情况。

dp[i][j].next表示当前的最优解是由哪一种状态转移过来的。

代码又写锉了。。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <queue>

#include <cmath>

#include <stack>

#include <map>

#pragma comment(linker, "/STACK:1024000000");

#define EPS (1e-8)

#define LL long long

#define ULL unsigned long long

#define _LL __int64

#define _INF 0x3f3f3f3f

#define Mod 9999991

using namespace std;

struct N

{

    bool mark;

    int ans,dig,next;

}dp[111][10000];

char s[110];

int mod1[110],mod2[110];

void Out(int site,int mod)

{

    if(mod == -1)

        return ;

    printf("%d",dp[site][mod].dig);

    Out(site+1,dp[site][mod].next);

}

int main()

{

    int k,i,j,l;

    while(scanf("%s %d",s+1,&k) != EOF)

    {

        for(i = 1; s[i] != '\0'; ++i)

        {

            for(j = 0; j < k; ++j)

                dp[i][j].mark = false;

        }

        mod1[0] = 0,mod2[0] = 1%k;

        for(i = 1;s[i] != '\0'; ++i)

        {

            mod1[i] = (mod1[i-1]*10 + s[i]-'0')%k;

            mod2[i] = (mod2[i-1]*10)%k;

        }

        int site = strlen(s+1);

        for(i = 0 ;i <= 9 ; ++i)

        {

            if(dp[site][i%k].mark == false)

            {

                dp[site][i%k].mark = true;

                dp[site][i%k].ans = (i == s[site]-'0' ?  0 : 1);

                dp[site][i%k].dig = i;

                dp[site][i%k].next = -1;

            }

            else

            {

                if((i == s[site]-'0' ?  0 : 1) < dp[site][i%k].ans)

                {

                    dp[site][i%k].ans = (i == s[site]-'0' ?  0 : 1);

                    dp[site][i%k].dig = i;

                }

                else if((i == s[site]-'0' ?  0 : 1) == dp[site][i%k].ans && i <= dp[site][i%k].dig)

                {

                    dp[site][i%k].dig = i;

                }

            }

        }

        int mod;

        int len = strlen(s+1);

        for(--site ; site >= 1 ; --site)

        {

            mod = 0;

            for(i = (site == 1 ? 1 : 0);i <= 9; ++i)

            {

                for(j = 0;j < k; ++j)

                {

                    if(dp[site+1][j].mark == true)

                    {

                        if(dp[site][(mod + i*mod2[len-site] + j)%k].mark == false)

                        {

                            dp[site][(mod + i*mod2[len-site] + j)%k].mark = true;

                            dp[site][(mod + i*mod2[len-site] + j)%k].ans = dp[site+1][j].ans+(s[site]-'0' == i ? 0 :1);

                            dp[site][(mod + i*mod2[len-site] + j)%k].dig = i;

                            dp[site][(mod + i*mod2[len-site] + j)%k].next = j;

                        }

                        else

                        {

                            if(dp[site+1][j].ans+(s[site]-'0' == i ? 0 :1) < dp[site][(mod + i*mod2[len-site] + j)%k].ans)

                            {

                                dp[site][(mod + i*mod2[len-site] + j)%k].ans = dp[site+1][j].ans+(s[site]-'0' == i ? 0 :1);

                                dp[site][(mod + i*mod2[len-site] + j)%k].dig = i;

                                dp[site][(mod + i*mod2[len-site] + j)%k].next = j;

                            }

                            else if(dp[site+1][j].ans+(s[site]-'0' == i ? 0 :1) == dp[site][(mod + i*mod2[len-site] + j)%k].ans && i < dp[site][(mod + i*mod2[len-site] + j)%k].dig)

                            {

                                dp[site][(mod + i*mod2[len-site] + j)%k].dig = i;

                                dp[site][(mod + i*mod2[len-site] + j)%k].next = j;

                            }

                        }

                    }

                }

            }

        }

        Out(1,0);

        puts("");

//        cout<<len<<endl;

//        for(i = 1;i <= len; ++i)

//        {

//            for(j = 0;j < k; ++j)

//            {

//                if(dp[i][j].mark)

//                    printf("%2d ",dp[i][j].next);

//                else

//                    printf("   ");

//            }

//            puts(" * ");

//        }

//

//        puts("");

//

//        for(i = 1;i <= len; ++i)

//        {

//            for(j = 0;j < k; ++j)

//            {

//                if(dp[i][j].mark)

//                    printf("%2d ",dp[i][j].dig);

//                else

//                    printf("   ");

//            }

//            puts(" * ");

//        }

//

//        puts("");

//

//

//        for(i = 1;i <= len; ++i)

//        {

//            for(j = 0;j < k; ++j)

//            {

//                if(dp[i][j].mark)

//                    printf("%2d ",dp[i][j].ans);

//                else

//                    printf("   ");

//            }

//            puts(" * ");

//        }

    }

    return 0;

}