POJ1011 stick

PS: 經典的搜索剪枝。

POJ 上用G++ Runtime error 無數次， C++ AC。 原來是因為排序函數的問題。

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 70;
bool dfs(int x, int y, int z,  int w, int t);
bool vis[maxn];
int d[maxn]; // data.
int n, length;
bool cmp(int a, int b) {
    if(a > b) return true; // G++ Runtime error.
    return false;
}

int main()
{
    int sum;
    while(scanf("%d", &n)!=EOF && n) {
        sum = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &d[i]);
            sum += d[i];
        }
        sort(d+1, d+n+1, cmp);
        bool res = false;
        for(int i = d[1]; i <= sum/2; i++) {
            if(sum%i==0) {
                memset(vis, false, sizeof(vis));
                vis[1] = true;
                res = dfs(2, i-d[1], 0, sum/i, i);
                vis[1] = false;
                if(res) {
                    printf("%d\n", i);
                    break;
                }
            }
        }
        if(!res) printf("%d\n", sum);
    }
    return 0;
}
bool dfs(int cur, int remain, int cnt, int total, int bound) {
    if(remain==0) {
        if(cnt+1>=total-1) return true;
       // if(cur>=n+1) return false;
        for(cur=1; vis[cur]; cur++);
        vis[cur]=true;
        if(dfs(cur+1, bound-d[cur], cnt+1, total, bound))
            return true;
        vis[cur]=false;
        return false;
    }
    else {
        if(cur>=n+1) return false; // wa.
        for(int i = cur; i <= n ; i++) {
            if(vis[i]) continue;
           if(!vis[i-1] && d[i]==d[i-1]) continue;
           if(d[i]>remain) continue;
           vis[i]=true;
           bool res = dfs(i+1, remain-d[i], cnt, total, bound);
           vis[i]=false;
           if(res) return true;
        }
        return false;
    }
    return false;
}
/**
64
40 40 30 35 35 26 15 40 40 40 40 40 40 40 40 40 40 40 40 40 40
40 40 43 42 42 41 10 4 40 40 40 40 40 40 40 40 40 40 40 40 40
40 25 39 46 40 10 4 40 40 37 18 17 16 15 40 40 40 40 40 40 40
40
key:454.
9
15 4 3 1 2 8 11 8 8
Key:20.
9
1 2 5 1 2 5 1 2 5
key:6.
**/