POJ 2718 Smallest Difference(dfs，剪枝)
枚举两个排列以及有那些数字，用dfs比较灵活。
dfs1是枚举长度短小的那个数字，dfs2会枚举到比较大的数字，然后我们希望低位数字的差尽量大，
后面最优全是0，如果全是0都没有当前ans小的话就剪掉。
（第1个dfs完了，忘了加return。。。
#include<cstdio> #include<iostream> #include<string> #include<cstring> #include<queue> #include<vector> #include<stack> #include<vector> #include<map> #include<set> #include<algorithm> using namespace std; //string line; int line[11]; bool vis[11]; int len1,len2, n; const int wei[] = {1,10,100,1000,10000,100000,1000000}; int ans; int num1; void dfs2(int d,int cur) { if(abs(num1 - cur*wei[len2-d]) >= ans) return; if(d == len2){ ans = min(ans,abs(num1-cur)); return; } for(int j = 0; j < n; j++){ if(!vis[j]){ vis[j] = true; dfs2(d+1,cur*10+line[j]); vis[j] = false; } } } //permutation void dfs1(int d,int cur) { if(d == len1){ num1 = cur; for(int fi = 0; fi < n; fi++){ if(!vis[fi] && line[fi]){ vis[fi] = true; dfs2(1,line[fi]); vis[fi] = false; } } return; } for(int j = 0; j < n; j++){ if(!vis[j]){ vis[j] = true; dfs1(d+1,cur*10+line[j]); vis[j] = false; } } } //0 2 , 0 3 //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int T; scanf("%d",&T); scanf(" "); while(T--){ char ch; n = 0; while((ch = getchar())!= ' '){ if(isdigit(ch)){ line[n++] = ch-'0'; } } if(n == 2){ printf("%d ",abs(line[0]-line[1])); continue; } len1 = n>>1; len2 = n-len1; ans = 1<<30; memset(vis,0,sizeof(vis)); for(int fi = 0; fi < n; fi++){ if(line[fi]){ vis[fi] = true; dfs1(1,line[fi]); vis[fi] = false; } } printf("%d ",ans); } return 0; }