4.1中的奶牛家秘术和Fence Rails都是要加好几个剪枝才可以AC的问题

搜索对象:每个栅栏(rail)对应那个Board(可能的深度太大而答案很可能在很浅的地方,所以迭代深度去找(DFSID),如果某个深度找到一个可行解,立刻退出,再搜索下一个深度)

一般优化都可以从以下3点考虑:

1.可行性剪枝   如果我们预料到某种情况无论再怎么搜索也得不到可行解,那就直接退出

2.最优化剪枝   如果我们预料到某种情况无论再怎么走索也得不到比当前最优解更优的解,那也直接退出

3.搜索顺序      良好的搜索顺序会更快的找到答案

其他技巧因问题而不同

那么Fence Rails可以这样剪枝:

1.可行性:     如果当前剩下的不可用的Board(即不能再切出rails的board)的和比board总面积减去rails的总面积还大,那肯定不可行(通俗地讲就是不能再装Rails的面积比装满所有rails剩下来的面积大)

2.搜索顺序:  容易想到,如果刚开始的时候就用大的rail塞到较小的board中,很快就能找到可行解

3.注意有很多重复,考虑到重复的元素位置不同没有影响,所以如果上一个元素和该元素相同,那么所在的board就直接从上一个开始枚举

这样就可以AC了

我的代码(有些慢):

/*
ID:alertya1
PROG:fence8
LANG:C++
*/
#include <fstream>
#include <algorithm>
#include <set>
using namespace std;
ifstream fin("fence8.in");
ofstream fout("fence8.out");
int N,R,A[2048],Cf[60],Now[60],Pre[2048],Max,Sums,Limit,Tot;
bool flag;
bool Cmp(int a,int b)
{
	return a>b;
}
void Initialize()
{
int i;
	fin>>N;
	for(i=1;i<=N;i++)
	{
		fin>>Cf[i];
		Tot+=Cf[i];
	}
	sort(Cf+1,Cf+N+1);
	fin>>R;
	for(i=1;i<=R;i++)
		fin>>A[i];
	sort(A+1,A+R+1);
	for(i=1;i<=R;i++)
		if(A[i]>Cf[N])
			break;
	R=i-1;
	for(i=1;i<=R;i++)
		Pre[i]=Pre[i-1]+A[i];
}

void DFS(int pos,int Prev)
{
int i,st,R=0;
	if(Sums>Tot-Pre[Limit])
		return;
	if(pos>Limit)
		flag=true;
	if(flag)
		return;
	st=1;
	if(A[Limit-pos+1]==A[Limit-pos+2])
		st=Prev;
	for(i=st;i<=N;i++)
		if(A[Limit-pos+1]<=Cf[i])
		{
			Cf[i]-=A[Limit-pos+1];
			if(Cf[i]<A[1])
				Sums+=Cf[i];
			DFS(pos+1,i);
			if(Cf[i]<A[1])
				Sums-=Cf[i];
			Cf[i]+=A[Limit-pos+1];
		}
}

int main()
{
	Initialize();
	
	for(Limit=1;Limit<=R;Limit++)
	{
		flag=false;
		DFS(1,1);
		if(!flag)
			break;
	}
	fout<<Limit-1<<endl;
	fin.close();
	fout.close();
	return 0;
}

当然，John可以切木板。因此，一个9英尺的木板可以切成一个5英尺和一个4英尺的木料 (当然也能切成3个3英尺的，等等)。John有一把（完美的）梦之锯，因此他在切木料时，不会有木料的损失。

所需要的栅栏长度可能会有重复（比如，一个3英尺和另一个3英尺长的栅栏可能同时都需要）。所需要的木料规格都已经给定。你不必切出更多木料，那没有用。

格式

PROGRAM NAME: fence8

INPUT FORMAT:

(file fence8.in)

第1行: N (1 <= N <= 50), 表示提供的木板的数目

第2行到第N+1行: N行，每行包括一个整数，表示各个木板的长度。

第N+2行: R (1 <= R <= 1023), 所需木料的数目

第N+3行到第N+R+2行: R行，每行包括一个整数(1 <= ri <= 128)表示所需木料的长度。

OUTPUT FORMAT:

(file fence8.out)

只有一行，一个数字，表示能切出的最多的所需木料的数目。当然，并不是任何时候都能切出所有所需木料。

SAMPLE INPUT

4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30 SAMPLE OUTPUT  

7