1455.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<iostream.h>
#include<algorithm>
#include<string>
#define MAX 66
using namespace std;
int stick[MAX];
int num, slen, snum, total, len;
bool use[MAX], f;
bool cmp(int a, int b)
{
    return a > b;
}
void dfs(int a){
	int i;
    if(snum == total / len)
	{
        f = true;
        return;
    }
    if(a == 0)
	{
        slen = 0;
        for(i = snum; i < num; i++)
		{
            if(!use[i])
			{
                if(stick[i] == len)
				{
                    use[i] = true;
                    snum++;
                    dfs(0);
                    use[i] = false;
                    snum--;
                }
                else
				{
                    use[i] = true;
                    slen = stick[i];
                    dfs(i + 1);
                    use[i] = false;
                    slen = 0;
                }
                if(f)
				{
                    return;
				}
                break;
            }
        }
    }
    else
	{
        for(i = a; i < num; i++)
		{
            if(f)
			{
                return;
			}
            if(!use[i] && (use[i - 1] || stick[i] != stick[i - 1]))
			{
                if(stick[i] + slen == len)
				{
                    use[i] = true;
                    snum++;
                    dfs(0);
                    use[i] = false;
                    snum--;
                    slen = len - stick[i];
                    if(f)
					{
                        return;
					}
                    break;
                }
                else if(stick[i] + slen < len)
				{
                    use[i] = true;
                    slen += stick[i];
                    dfs(i + 1);
                    use[i] = false;
                    slen -= stick[i];
                    if(f)
					{
                        return;
					}
                }
            }
        }
    }
}
int main()
{
    int i, j, k;
    while(scanf("%d", &num) == 1 && num)
	{
        memset(stick, 0, sizeof(stick));
		memset(use, false, sizeof(use));
        total = 0;
        for(j = 0, i = 0; i < num; i++)
		{
            scanf("%d", &k);
            if (k <= 50)
			{
				stick[j++] = k;
				total += k;
			}
        }
		num = j;
		if (num == 0)
		{
			printf("0\n");
			continue;
		}
        sort(stick, stick + num, cmp);
        len = stick[0];
        slen = 0;
		snum = 0;
        f = false;
        while(!f)
		{
            while(total % len)
			{
                len++;
			}
            dfs(0);
            if(f)
			{
                break;
			}
            len++;
        }
        printf("%d\n",len);
    }
	return 0;
}