【普及一】小猫爬山WA16

常规
,
1 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

int n, w, a[20], ans = 20;

void dfs(int dep, int k, int sum)
{
	if(k > ans) return ;
	if(dep > n)
	{
		ans = min(ans, k);
		return ;
	}
	if(sum + a[dep] > w) dfs(dep + 1, k + 1, a[dep]);
	else dfs(dep + 1, k, sum + a[dep]);
}

int main()
{
	cin >> n >> w;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	dfs(1, 1, 0);
	cout << ans << endl;
	return 0;
}
3 个赞
2

这里考虑不够全面，小猫做选择的时候，不只是这两个选择。
如果现有k个缆车，那么小猫dep可以选择 1~k缆车(前提坐得下)
也可以选择独自到k+1个缆车上

2 个赞
3 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

int n, w, a[20], l[20], ans = 20;

void dfs(int dep, int k)
{
	if(k > ans) return ;
	if(dep > n)
	{
		ans = min(ans, k);
		return ;
	}
	for(int i = 1; i <= k; i++)
		if(l[i] + a[dep] < w)
		{
			l[i] += a[dep];
			dfs(dep + 1, k);	
		} 
	l[k + 1] = a[dep];
	dfs(dep + 1, k + 1);
	
}

int main()
{
	cin >> n >> w;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	dfs(1, 1);
	cout << ans << endl;
	return 0;
}

改了之后WA8分

2 个赞
4

回溯时数组影响没撤销

1 个赞