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

Sticks POJ - 1011

程序员文章站 2022-03-12 09:50:56
...

Sticks POJ - 1011

借鉴的这个人的

题解:
说一下三条剪枝函数,当运行到剪枝函数,可以理解为搜索失败了。
1.第一个剪枝:如果当前搜索a[i]时,发现因为a[i]的原因不能使木棍分成等长的几部分,当goal等于a[i]时,也就不需要在搜索了。
2,第二个剪枝:(引上面博客内容)假设 要搜索目标长度为 7 :绳长有 7 6 3 2 2.
假设 第一个7 搜索完,接下来搜索6 发现6没有1来配对,程序会接下来搜索 3 2 2,但很明显根本不需要搜索后面的,前面有一个用不上,后面就不需要再搜索了。
3.第三个:如果a[i]搜索失败了,若a[i+1] == a[i],就不用搜索了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

bool cmp(int a,int b)
{
    return a>b;
}

int n,a[70],mins,maxn,sum,vis[70];
bool flag;

void dfs(int goal,int num,int k)
{
    if(flag) return;
    if(num == n&&goal == 0) {flag = true; return;}
    if(goal == 0&&num<n) dfs(maxn,num,0);

    for(int i = k ; i < n ; i++)
    {
        if(!flag&&!vis[i]&&a[i]<=goal)
        {
            vis[i] = 1;
            dfs(goal-a[i],num+1,i+1);
            vis[i] = 0;

            //运行到这一步,一般可以理解为上面搜索失败了; 
            if(goal == a[i]) return;
            if(goal == maxn) return;
            while(a[i] == a[i+1]) i++;
        }
    }

}


int main()
{
    while(~scanf("%d",&n))
    {
        if(n == 0) break;
        sum = 0;
        flag = false;
        for(int i = 0 ; i < n ; i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        sort(a,a+n,cmp);        
        if(a[0]>sum-a[0])
        {
            cout<<sum<<endl;
            continue;
        }
        maxn = a[0];
        while(maxn<sum)
        {
            memset(vis,0,sizeof(vis));
            while(sum%maxn != 0) maxn++;//这里不能写成if; 
            dfs(maxn,0,0);
            if(flag) break;
            maxn++;
        }
        cout<<maxn<<endl;
    }
    return 0;



}