poj2718 Smallest Difference（dfs+特判，还可以贪心更快）

其实不太理解为什么10超时了。。

这题似乎是有贪心优化的方法的，我下面直接暴力了。。

暴力之余要特判两个点：1.超时点就是n=10的时候，直接算一下247

　　　　　　　　　　　　2.WA点就是如果有两个数，且一个为0，那样不算先导零，结果按我的代码也是要特判的。

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<stack>

 #include<map>

 #include<set>

 #define lson l, m, rt<<1

 #define rson m+1, r, rt<<1|1

 #define INF 0x3f3f3f3f

 typedef unsigned long long ll;

 using namespace std;

 char s[];

 int a[], vis[], sum1, sum2, mini, n;

 void dfs(int cur)

 {

     if(cur < n/){

         for(int i = ; i < n; i++){

             if(cur == &&a[i] == ) continue;//排除先导零

             if(!vis[i]){

                 vis[i] = ;

                 sum1 = sum1*+a[i];

                 cur++;

                 dfs(cur);

                 sum1 = (sum1-a[i])/;

                 cur--;

                 vis[i] = ;

             }

         }

     }

     else if(cur == n){

         mini = min(abs(sum2-sum1), mini);

     }

     else{

         for(int i = ; i < n; i++){

             if(cur == n/&&a[i] == ) continue;//排除先导零

             if(!vis[i]){

                 vis[i] = ;

                 sum2 = sum2*+a[i];

                 cur++;

                 dfs(cur);

                 sum2 = (sum2-a[i])/;

                 cur--;

                 vis[i] = ;

             }

         }

     }

 }

 int main()

 {

     int t;

     scanf("%d", &t);

     char c = getchar();

     while(t--){

         gets(s);

         int len = strlen(s);

         n=, sum1 = , sum2 = , mini = INF;

         for(int i = ; i < len; i++){

             a[n++] = s[i++]-'';

         }

         if(n == ){//不特判就超时，只有这一条超时

             printf("247\n");

             continue;

         }

         else if(n == &&(a[]==||a[]==)){//如果只有两位，且有一位为0也要特判

             printf("%d\n", max(a[], a[]));

             continue;

         }

         dfs();

         printf("%d\n", mini);

     }

 }