poj 3373 Changing Digits 夜

http://poj.org/problem?id=3373

DFS+强力剪枝

伤不起呀 自己写怎么都写不出来 最后还看开了别人的解题报告

思维能力还是不够呀

推荐解题报告：http://blog.csdn.net/lyy289065406/article/details/6698787

代码及其注释：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<algorithm>
#include<set>

using namespace std;

const int N=105;
char s[N];
int a[N];
int change[N][10005];//表示 区间0~i 模为j 改变多少数是无解的
int K;
int n;
int mod[N][10];//从0位开始 第i位为 j 时对K取得模
int dpmod(int x,int k)
{
    if(mod[x][k]!=-1)
    return mod[x][k];
    if(x==0)
    {
        mod[x][k]=k%K;
        return mod[x][k];
    }
    mod[x][k]=(dpmod(x-1,k)*10)%K;
    return mod[x][k];
}
int findmod()//求当前数组对K的模
{
    int m=0;
    for(int i=0;i<n;++i)
    {
        m=(m+dpmod(i,a[i]))%K;
    }
    return m;
}
int I=1;
bool Dfs(int x,int renum,int Mod)//0~x区间  re准许改变几个 Mod为模
{
    if(Mod==0)
    return true;
    if(x<0||renum<=0)
    return false;
    if(renum<=change[x][Mod]||renum>x+1)//关键剪枝
    return false;
    for(int i=x;i>=0;--i)//找小的  从高位到低位
    {
        for(int j=(i<n-1)?0:1;j<a[i];++j)
        {

            int temp=a[i];
            a[i]=j;
            int k=(Mod-mod[i][temp]+mod[i][j]+K)%K;
            if(Dfs(i-1,renum-1,k))
            return true;
            a[i]=temp;
        }
    }
    for(int i=0;i<=x;++i) 找大的 从低位到高位
    {
        for(int j=a[i]+1;j<10;++j)
        {
            int temp=a[i];
            a[i]=j;
            int k=(Mod-mod[i][temp]+mod[i][j]+K)%K;
            if(Dfs(i-1,renum-1,k))
            return true;
            a[i]=temp;
        }
    }
    change[x][Mod]=renum;//记录
    return false;
}
void begin()
{
    for(int j=0;j<10;++j)
    {
        dpmod(n-1,j);
    }
}
int main()
{
   while(scanf("%s",s)!=EOF)
   {
       scanf("%d",&K);
       getchar();
       n=strlen(s);
       for(int i=0;i<n;++i)
       {
           a[i]=s[n-i-1]-'0';
       }
       memset(mod,-1,sizeof(mod));
       memset(change,-1,sizeof(change));
       begin();
        int k=findmod();
        for(int i=1;i<=n;++i)
        {
            if(Dfs(n-1,i,k))
            {break;}
        }
       for(int i=n-1;i>=0;--i)
       printf("%d",a[i]);
       printf("\n");
   }
   return 0;
}