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
更多推荐
poj 3373 Changing Digits (DFS+剪枝)
发布评论