hdu1455 Sticks(dfs)

发布于 / Algorithm / 0 条评论

Sticks
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1455
Problem Description
George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input
The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

Output
The output file contains the smallest possible length of original sticks, one per line.

Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output
6
5

 

将n个数分成m堆,每一堆的和都相等为H,求H最小为多少。

5

1 2 3 4 5

最短的就是  1+4=2+3=5

初始就是3根长度为5的绳子,题目没要求求多少根,只求长度最小为多少。

 

 

主要是dfs函数中那三个if里的剪枝。

首先要明白,什么时候会回溯,就是当dfs进去搜索,发现没有符合的,才会回溯。

也就是说,只有当当前的数不符合的时候才会回溯出来。

第一条剪枝:

如果你剩余的长度和当前长度相等,就没有必要搜索,也就是说当你剩余长度为3,接着搜索3,发现不符合,就不需要搜索剩下能构成3的(比如2+1,1+1+1等)

第二条剪枝:(重要的)

意思是如果剩余的长度等于绳子总长度,而当前不符合,就不需要接着搜索。

也就是说,接下来搜索的长度就是绳子目标长度,而你当前长度根本用不上,那就肯定不符合了。

例子:  假设 要搜索目标长度为 7  :绳长有 7 6 3 2 2.

假设 第一个7 搜索完,接下来搜索6 发现6没有1来配对,程序会接下来搜索 3 2 2,但很明显根本不需要搜索后面的,前面有一个用不上,后面就不需要再搜索了。

第三条剪枝:

如果当前长度的不满足,那么相同长度的就不需要再次去搜索

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int n,maxx,sum,arr[70];
bool ispos,vis[70];
// 由大到小排序
bool cmp(int a,int b)
{
    return a>b;
}
 
 
void dfs(int res,int js,int pos)
{
    // 找到答案,返回
    if(ispos==1)    return;
    // 如果所有都被选择 ispos置1,表示找到
    if(js==n)   {ispos=1;return;}
    // 如果res=0 且并非所有都被选择,则继续将maxx   dfs
    if(res==0 && js<n)  dfs(maxx,js,0);
 
    int i;
    for(i=pos;i<n;++i)
    {
        if(!ispos && !vis[i] && arr[i]<=res)
        {
            vis[i]=1;
            dfs(res-arr[i],js+1,pos);
            vis[i]=0;
 
            // 这个去掉 +40MS   
            if(res==arr[i]) return;
            // 这个去掉,TLE。。  
            if(res==maxx)   return;
            // 这个剪枝去掉了,+100MS
            while(arr[i]==arr[i+1]) ++i;
        }
    }
 
}
 
int main()
{
    int i;
    while(cin>>n)
    {
        if(!n)  break;
        sum=0;
        for(i=0;i<n;++i)
        {
            cin>>arr[i];
            sum+=arr[i];
        }
        sort(arr,arr+n,cmp);
        maxx=arr[0];
 
        // 剪枝:如果最长的长度大于剩余所有长度和,则答案就是他们的和
        //(这个去掉了也可以,耗时没有变化 = 。=,就是说不写也可以)
        if(maxx>sum-maxx)
        {
           cout<<sum<<endl;
            continue;
        }
        ispos=0;
        while(!ispos)
        {
            // 剪枝: 如果所有长度总和 对 目标长度 取模不为0 ,则目标长度一定不是答案,这个必须有
            // 这个如果去掉,耗时增多不说,对后面剪枝影响,会导致WA
            while(sum%maxx!=0) {++maxx;}
 
            memset(vis,0,sizeof(vis));
            dfs(maxx,0,0);
            if(ispos)   break;
            ++maxx;
        }
        cout<<maxx<<endl;
    }
    return 0;
}

 

转自:

https://blog.csdn.net/lttree/article/details/23103573

转载原创文章请注明,转载自: 静沐暖阳 » hdu1455 Sticks(dfs)
Not Comment Found