【POJ】1011 Stick

题目描述：
若干木棒被截成最多64段，要把它们都组合起来，找到原棒的最短长度，如被截成1，2，3。则最短棒长为3，若被截成1，6，15，则最短棒长为22。
思路：
每段长非递减排序后，由大开始选，依次加到与枚举的原棒长相等，并标记每个已用于组合的小段。直到所有都使用，并且能组合为枚举的最小原长。否则原棒长要枚举到总榜长为止。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifndef ONLINE_JUDGE
#include<time.h>
#endif

#define YES 1
#define NO 0



int stick[70][2];//二维数组分别存每截棒长和(排序后)下一个不同于它的长度的位置(行标)
int used[70];//记录每截棒是否已被用于组合原棒
int min_stick_len;//最短原棒长
int m;//所有原棒被截得的总段数
int stick_num;//原棒的数量

int compare(const int *a, const int *b)
{
    return *(int*)b - *(int *)a;
}

void Init_Next()
{
    int i, j, t;
    for (i=0; i<m; i=j)
    {
        t = i;
        j = i+1;
        while (stick[j][0] == stick[t][0])
        {
            j++;
        }
        while (t<j)
        {
            stick[t++][1] = j;
        }
    }
}

//查找组合可能,形参为当前可组合木棍的位置,当前组合的长度,当前已组合的木棍数量
int dfs(int cur, int cur_len, int num)
{
    int i, start;
    start = (cur_len==0 ? YES : NO);
    if (num == stick_num)
    {
        return YES;
    }
    for (i=cur; i<m; i++)//从头到尾枚举
    {
        if (used[i])
        {
            continue;
        }
        if (cur_len + stick[i][0] < min_stick_len)//组合长度不足最短原木棒长度
        {
            used[i] = YES;
            if (dfs(i, cur_len + stick[i][0], num))//继续加长度组合
            {
                return YES;
            }
            used[i] = NO;
            if (start)//如果组合每根原木棒选的第一个长度不符合就跳出选下一个
            {
                return NO;
            }
            i = stick[i][1]-1;//如果同种长度的一种不满足, 则直接查找下一个不同长度的木棒
        }
        else if (cur_len + stick[i][0] == min_stick_len)//组合长度等于最短原木棒长度
        {
            used[i] = YES;
            if (dfs(-1, 0, num+1))//长木棒数加一, 再次搜索
            {
                return YES;
            }
            used[i] = NO;
            return NO;
        }
    }//end of for
    return NO;
}

int main()
{
    int i, j, n;
    int sum;//木棒总长
     int cur = 0, cur_len = 0, num = 0;
     #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    #endif
    while (scanf("%d", &m), m)
    {
        memset(stick, 0, sizeof(stick));
        sum = 0;
        for (i=0; i<m; i++)
        {
            scanf("%d", &stick[i][0]);
            sum += stick[i][0];
        }
        qsort(stick, m, sizeof(stick[i]), compare);//每截棒长非递减排序
        //查找排序后的每截木棍后第一个长度不同的木棍的位置
        Init_Next();
        for (min_stick_len=stick[0][0]; min_stick_len<=sum; min_stick_len++)
        {
            memset(used, 0, sizeof(used));
            if (sum % min_stick_len != 0)//最短原棒长必然是总长的度的因子
            {
                continue ;
            }
            stick_num = sum / min_stick_len;
            if (dfs(cur, cur_len, num+1))
            {
                printf("%dn", min_stick_len);
                break;
            }
        }
    }
       #ifndef ONLINE_JUDGE
    printf("used time = %.3lfn",(double)clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}
//end of program.

//要搜索各种情况, 必须排序后再组合
//因为当判断某一长度不满足组合情况后,就没必要再次判断与它长度相同的其它棒,可直接跳到下一个长度不同的棒.
//所以加70行的i = stick[i][1]-1;会比while(stick[i][0] == stick[i+1][0]) i++;快0.12s左右.

2010-10-02 13:39 发表于百度空间，今搬至CU。