poj 3373 Changing Digits (DFS+剪枝)

poj 3373 Changing Digits (DFS+剪枝)

=3373


详解见：

/*
这道题想了半天越想月觉的麻烦，后来实在是写不出来就，参考了一下别人烦人代码，在这加了数组f[a][b]=c;a 表示位置，b表示余数，c表示剩余的次数，含义是 在a这个位置，余数为b的情况下
无论是往较大的数改变，还是娇小的数，在改变此时《=c情况下，找不到满足要求的数
*/
#include<stdio.h>
#include<string.h>
int mod[110][10],test[110],nu[110],f[110][12000];
char str[110];
int k,len;
void init()
{int i,j;for(i=0;i<10;i++)mod[0][i]=i%k;for(i=1;i<len;i++){for(j=0;j<10;j++){mod[i][j]=(mod[i-1][j]*10)%k;}}memset(f,0,sizeof(f));
}
bool DFS(int pos,int num,int m )
{int i,j;if(m==0){for(i=len-1;i>=0;i--)printf("%d",test[i]);printf("n");return true;}if(pos<0||num<=f[pos][m]||num==0)return false;for(i=pos;i>=0;i--){for(j=0;j<nu[i];j++){if(i==len-1&&j==0)continue;test[i]=j;int a=(m-(mod[i][nu[i]]-mod[i][j])+k)%k;if(DFS(i-1,num-1,a))return true;}test[i]=nu[i];}for(i=0;i<=pos;i++){for(j=nu[i]+1;j<10;j++){if(i==len-1&&j==0)continue;test[i]=j;int a=(m+(mod[i][j]-mod[i][nu[i]]))%k;if(DFS(i-1,num-1,a))return true;}test[i]=nu[i];}f[pos][m]=num;return false;}
void solve()
{int i;int m=0;for(i=0;i<len;i++){test[i]=nu[i]=str[len-i-1]-'0';m+=mod[i][nu[i]];m%=k;}for(i=1;i<=len;i++){if(DFS(len-1,i,m))return;}
}
int main()
{while(scanf("%s",str)!=EOF){scanf("%d",&k);len=strlen(str);init();solve();}
}

转载于:.html