首页 > > 程序设计 > C/C++ >

POJ 1011 Sticks解题报告

2018-08-17 09:37:25来源：博客园阅读 ()

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 should 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
题意：将一组等长木棒随机截断，知道截断后所有木棒长度，求截断前等长木棒最小长度
思路：从小到大枚举原长（从长度最长的木棍开始），DFS+剪枝
先求和，用总和除以原长得到需要拼凑的木棍数量，进行dfs判断可行性
     剪枝1：从长到短排序木棍，以便于优先用少量长木棍达到目标，减少dfs次数
     剪枝2：当拼凑一根等长木棍时，当前没用过的最长的木棍一定会成为第一个（因为每次的拼凑策略总会选择比上一个选择木棍短的棍子，如果没有选当前最长，说明当前最长一定不能当一组方案中的次长木棍） 
     剪枝3：每一次只考虑比上一次选择更短的木棍，因为比上一次选择更长的木棍已经考虑过。
     剪枝4：当一次拼凑有多个相同长度木棍可选时，只选择其中的一个进行搜索，以避免重复搜索
     剪枝5：没有必要用完所有的小棒拼出完整的m根等长木棒，只需要拼出m-1根，因为剩下的小棒无论如何是可以拼成的
     （剪枝6：如果当前已拼凑的长度加上所有输入数据的最小值还是大于要求的等长木棒长度，直接返回不可能。）
  代码（吐槽一下大多数16ms题解没优化完全)（0ms通过)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
#include<queue>
#include<vector>
#include<numeric>
using namespace std;
#define f(i,j) for(int i=1;i<=j;i++)
#define fx(i,k,j) for(int i=k;i<=j;i++)
#define gi(i) scanf("%d",&i)
#define gii(i,j) scanf("%d%d",&i,&j)
#define gi(i) scanf("%d",&i)
#define giii(i,j,k) scanf("%d%d%d",&i,&j,&k)
#define pi(i) printf("%d\n",i)
#define pii(i,j) printf("%d %d\n",i,j)
#define pf printf
#define inf 0x3f3f3f3f
#define clr(a) memset(a,0,sizeof(a))
#define fill(a,b) memset(a,b,sizeof(a))
#define _inline __attribute__((always_inline)) inline
typedef long long LL;
int n;
int vis[65];
int p[65];
int L;
int ndl;
int dfs(int tot,int stk,int sta){
    if(stk==ndl) return 1;
    if(tot==L) return dfs(0,stk+1,0);
    if(tot==0) sta=2;
    int last=0;
    if(tot+p[n]>L) return 0;
    fx(i,sta,n){
        if(!vis[i] && p[i]+tot<=L && p[i]!=last){
            last=p[i];
            vis[i]=1;
            if(dfs(tot+p[i],stk,i+1)) return 1;
            vis[i]=0;
            if(tot==0) return 0;
        }
    }
    return 0;
}
int main(){
while(gi(n)!=EOF){
    if(!n) return 0;
    f(i,n) gi(p[i]);
    sort(p+1,p+1+n,greater<int>());
    int MX=accumulate(p+1,p+1+n,0);
    int ans=-1;
    int M2=MX>>1;
    for(int i=p[1];i<=M2;i++){
        if(MX%i!=0) continue;
        L=i;
        ndl=MX/i-1;
        clr(vis);
        vis[1]=1;
        if(dfs(p[1],0,2)){
            ans=i;
            break;
        } 
    }
    pi(ans==-1?MX:ans);
}
}