poj 3373 Changing Digits(打表 + dfs + 剪枝 )

题意：给出两个数N和K，让你改变N中的某些数，找到一个数M，是的M%k== 0 ，并且找到的M要尽可能小。

思路：呃，其实我真的不擅长搜索，特别是搜，不过这题还是学到了很多东西。首先是一种大整数取模的方法。其实是参考着这篇解题报告学会的，

http://blog.csdn.net/lyy289065406/article/details/6698787 对于这题，他讲的很详细，我也是参考他的思路，所以就不说了。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <math.h>
#define  N 110
#define  M 14
using namespace std;

int mod[N][M] , n[N] , m[N] ;
int k , n_mod , len ;
char str[N] ;
int** vis ;

void Init( int len , int k )
{
    n_mod = 0 ;
    vis = new int*[len+1] ;
    for ( i = 0 ; i <= len ; i++ )
    {
        vis[i] = new int[k] ;
        memset( vis[i] , 0 , sizeof( int ) * k );
    }
    
    return  ;
}

void Mod_Table( int len )
{
    int i , j ;

    for ( i = 0 ; i <= 9 ; i++ )
    mod[0][i] = i % k ;

    for ( i = 1 ; i < len ; i++ )
    for ( j = 0 ; j <= 9 ; j++ )
    mod[i][j] = ( mod[i-1][j] * 10 ) % k ;

    return ;
}

void Cal_n_Mod( int len )
{
    int i ;

    for ( i = 0 ; i < len ; i++ )
    {
        n[i] = m[i] = str[len - i - 1] - '0' ;
        n_mod = ( n_mod + mod[i][n[i]] ) % k ;
    }

    return  ;
}

int dfs( int pos , int res , int m_mod)
{
    if ( m_mod == 0 )//如果m_mod为0的话说明找到了最小的m
    return 1 ;

    if( pos < 0 || res == 0 )//如果改变的长度为0或改变的位置为0 的话，返回false
    return 0 ;

    if ( res <= vis[pos][m_mod] )//剪枝，如果改变的长度已经小于在这个位置得到这个余数的话，直接返回
    return 0 ;

    int i , j ;
    for ( i = pos ; i >= 0 ; i-- )//因为n已经被逆序存放了，若要找的最小的m，应该从高位开始找。
    {
        for ( j = 0 ; j < n[i] ; j++ )//高位的变得越小越好，所以，从0开始
        {
            if ( i == len - 1 && j == 0 )
            continue ;

            int x_mod = ( m_mod - ( mod[i][m[i]] - mod[i][j] ) + k ) % k ;
            int tem = m[i] ;
            m[i] = j ;

            if ( dfs ( i - 1 , res - 1 , x_mod ))
            return 1 ;

            m[i] = tem ;
        }
    }

    for( i = 0 ; i <= pos ; i++  )//同理，找大于N的数，从低位开始找
    {
        for ( j = n[i] + 1 ; j <= 9 ; j++ )//并且从小的数字开始替换。这样可以保证找到的事最小的M
        {
            if ( i == len - 1  && j == 0 )
            continue ;

            int x_mod = ( m_mod + ( mod[i][j] - mod[i][m[i]] )) % k ;
            int tem = m[i] ;
            m[i] = j ;

            if ( dfs ( i - 1 , res - 1 , x_mod ))
            return 1 ;

            m[i] = tem ;
        }
    }

    vis[pos][m_mod] = res ;
    return 0 ;
}

int main()
{
    int i ;
    while( cin>>str>>k )
    {
        len = strlen( str );
        Init( len , k );//初始化数组vis
        Mod_Table( len );//打表，用来求 m % k ;
        Cal_n_Mod( len );//计算 n % k ;
        
        //dfs 深搜
        for ( i = 1 ; i <= len ; i++ )
        if ( dfs ( len - 1 , i , n_mod ))
        break;

        for ( i = 0 ; i < len ; i++ )
        printf ( "%d" , m[len-i-1] );
        printf ( "\n" );

        delete []vis ;
    }
    return 0 ;
}