【DG特長生2012 T3】【SSL 2240】栅欄的木料

栅欄的木料

題目連結：SSL 2240

題目大意

給你一些數，你可以把它拆開成幾個加起來等于它的數。

然後再給你一些目标數，問你可以得到多少個其中這樣的數。

如果兩個目标數相同，那你如果要得到這兩個，就要得到兩個這樣的數。

思路

這道題我們其實可以直接暴力 dfs，問題是如何剪枝。

首先我們要發現你選的數肯定是從小到大開始選，能選就選。

因為如果你選了大的而不選小的，那這個大的用這個小的數代替，也是可行的，還會留下更多的空間。

那你會發現可以枚舉選前面多少個數，看能不能被湊出來。

然後你會發現到一定的位置就湊不出來了，再往後也湊不出來，那它就滿足了單調性，可以進行二分。

那這裡優化完了，我們就考慮如何看這些數能不能湊出你要的那些數。

那我們就 dfs 暴力，對于每個要的數看它可以由那個數拆出來給。

但是這樣很明顯就會逾時，于是我們考慮剪枝優化：

剪枝1：如果你要湊出的數的和大于你有的數的和，那很明顯就不能湊出。

剪枝2：有一些你有的出連最小的要湊出的數都湊不出，那這個木闆可以直接舍去不要。

剪枝3：在操作的過程總如果有一些數被減到來弄最小的需要的木闆都湊不出，那這個木闆就直接不要了。

剪枝4：我們可以搞一個變量，記錄還可以損失多少的數，然後操作的時候維護一下。如果它要被減到負數，那這種方案就是不可行的。

剪枝5：我們可以把給你的數和要拼的數都從小到大排序一下，算的時候會減少時間，也可以根據這個進行下面的剪枝6。

剪枝6：如果兩個要拼的數一樣大，那你可以直接從拼出上一個要拼的數的位置開始看選哪個數拼出來。（因為根據前面，你前面的一定不能拼出它，就算能，它就像 a b ab ab 和 b a ba ba 一樣， a b ab ab 相等，它是重複的）

然後大概這麼搞搞就好了。

代碼

#include<cstdio>
#include<algorithm>
#define rr register

using namespace std;

int n, board[31], l, r, sb[31], wc, nb[31];
int m, wood[1051], ans, sw[1051];
bool kill[31];
int little;

bool cmp(int x, int y) {
	return x > y; 
}

bool dfs(int now, int last) {
	if (now < 1) return 1;
	
	//如果需要的數跟前面的一樣，那就直接從上次枚舉的繼續（剪枝）
	if (wood[now] != wood[now + 1])//否則就從開頭找
		last = little;
	
	for (int i = last; i <= n; i++)
		if (!kill[i] && nb[i] >= wood[now]) {
			nb[i] -= wood[now];
			if (nb[i] < wood[little]) {//這個數剩餘的不能拆出任何的你需要的數，連最小的都不可以
				if (wc < nb[i]) {//不能浪費這麼多的數，那就不能讓它選
					nb[i] += wood[now];//記得回溯
					continue;
				}
				wc -= nb[i];
				kill[i] = 1;//記錄這個木闆已經不能用了（因為你後面枚舉到的要的數會更大，就更加不可能用它）
				if (dfs(now - 1, i)) return 1;
				wc += nb[i];
				kill[i] = 0;
			}
			else {//用這個數拆
				if (dfs(now - 1, i)) return 1;
			}
			nb[i] += wood[now];
		}
	
	return 0;
}

bool check(int now) {
	if (sb[n] < sw[now]) return 0;//所有的數加起來都無法湊到你要的數的和，就不肯能有解（剪枝）
	wc = sb[n] - sw[now];//求出頂多可以浪費多少的數
	little = 1;
	while (board[little] < wood[1] && little <= n) {//有一些給出的數根本不能滿足任何要的數，直接舍去不管（剪枝）
													//【這個可以放到排序後，不用二分的時候搞】
		wc -= board[little];
		if (wc < 0) return 0;
		little++;
	}
	for (int i = 1; i <= n; i++)//初始化（一定要，因為你會中途退出）
		nb[i] = board[i], kill[i] = 0;
	return dfs(now, 1);
}

int main() {
//	freopen("fence.in", "r", stdin);
//	freopen("fence.out", "w", stdout);
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &board[i]);
	scanf("%d", &m);
	for (rr int i = 1; i <= m; i++) scanf("%d", &wood[i]);
	
	sort(board + 1, board + n + 1);//将他們從小到大排序（按一定順序搞時間會短，而且可以進行剪枝）
	sort(wood + 1, wood + m + 1);
	
	for (int i = 1; i <= n; i++)//算字首和
		sb[i] = sb[i - 1] + board[i];
	for (int i = 1; i <= m; i++)
		sw[i] = sw[i - 1] + wood[i];
	
	l = 1;
	r = m;//二分
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) {
			ans = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	
	printf("%d", ans);
	
	fclose(stdin);
	fclose(stdout); 
	
	return 0;
}