欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【暴力搜索】[POJ 1011]Sticks

程序员文章站 2024-03-23 21:44:34
...

首先这道题目有两个非常重要的剪枝1、如果当前放的是木块的第一个那如果当前dfs不成立,那么直接返回false因为每一个木板必定属于一个块,当他放第一个的时候如果可以放其他的其实是已经固定了的了,如果当前不成立那么不存在队友可以和他一起站对。2、就是如果当前这个和前一次进行dfs的木板长度一样,就跳过。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 64;
int n, sum, s[MAXN+10], Len, tot;
bool vis[MAXN+10];
bool dfs(int _len, int up, int count){
    if(count == tot) return true;
    int tp=-10000000;
    for(int i=up; i<n; i++){
        if(!vis[i]){
            if(s[i] == tp) continue;
            tp = s[i];
            vis[i] = true;
            if(_len + s[i] == Len){
                if(dfs(0, 0, count+1)) 
                    return true;
                return vis[i] = false;
            }
            else if(_len + s[i] < Len){
                if(dfs(_len+s[i], i+1, count))
                    return true;
                if(_len == 0) return vis[i] = false;
            }
            vis[i] = false;
        }
    }
    return false;
}
int main(){
    while(~scanf("%d", &n) && n){
        memset(vis, 0, sizeof vis);
        sum = 0;
        for(int i=0;i<n;i++){
            scanf("%d", &s[i]);
            sum += s[i];
        }
        sort(s, s+n);
        for(Len=s[n-1]; Len<=sum; Len++) 
            if(sum % Len == 0){
                tot = sum / Len;
                if(dfs(0, 0, 0)){
                    printf("%d\n", Len);
                    break;
                }
            }   
    }

    return 0;
}