9
15 3 2 11 4 1 8 8 8
比如就这个数据。答案是20
但是我的程序会把20否定掉。
因为按照降序排列，20的搜索会是15+4+1，这样的话剩下的数据就无法得出20的结论
本来应该是
15+3+2
8+8+4
11+8+1
关键点是不知道怎么改。。谢谢
#include <iostream>
#define MAX 65
using namespace std;

int stick[MAX];
int used[MAX];
int n, nLen;
int sumL, num;
int yes;

int cmp(const void *r1, const void *r2)
{
	return *(int *)r2 - *(int *)r1;
}


int dfs(int nl, int ni, int tn)//nl:现在的长度;tn:现在已经搜索成功的棍子数目;
//ni:搜索的坐标，既要搜索的棍子坐标;
{
	int i;
	if(tn == num){yes = 1; return 1;}
	for(i=ni; i<n; i++)
	{
		if(!used[i])
			nl+=stick[i];
		if(nl>nLen)
		{
			nl-=stick[i];
			continue;
		}
	    else if(nl==nLen)
		{
			tn++;
			used[i]=1;
			if(dfs(0, 0, tn))return 1;
			used[i]=0;//??
		}
		else if(nl<nLen)
		{
			used[i]=1;
			ni=i+1;
			if(dfs(nl, ni, tn))return 1;
			used[i]=0;
			break;
		}
		if(nl==0)break;
	}
	return 0;
}

	
int main()
{
	int i;
	while(scanf("%d", &n) && n)
	{
		sumL = 0;
		memset(stick, 0, sizeof(stick));
		//Input
		for(i=0; i<n; i++)
		{
			scanf("%d", &stick[i]);
			sumL += stick[i];
		}
		//Sort from big to small
		qsort(stick, n, sizeof(int), cmp);
		for(i=stick[0]; ;i++)
		{
			yes = 0;
			if(sumL%i == 0)
			{
				memset(used, 0, sizeof(used));
				num = sumL/i;
				nLen = i;
				dfs(0, 0, 0);
    			if(yes == 1)break;
			}
		}
		printf("%d\n", nLen);
	}
	return 0;
}

• 很着急呀。大牛水牛们帮帮我把 (0) windT 2009-01-25 10:55:03
  • Re:很着急呀。大牛水牛们帮帮我把 (88) windT 2009-01-25 11:07:23
    • 回溯过程中nl，tn，ni的值都是要恢复的。 (99) love8909 2009-01-25 11:57:21
      • Re:改了一遍。现在是TLE。。。。我崩溃了。。。。 (1340) windT 2009-01-25 12:40:31
        • Re:改了一遍。现在是TLE。。。。我崩溃了。。。。 (1508) ma3587 2009-05-13 13:04:31
        • Re:改了一遍。现在是TLE。。。。我崩溃了。。。。 (1508) xu422 2009-06-13 12:14:10
• Re:帮我看看怎么办吧！狂谢【附代码】，我知道哪里错了，不会改。 (9) lihaosky 2009-02-17 14:05:55