称重1

 题目描述

现有 n 个砝码，第i个砝码的重量为wi​，我们需要时使用这些砝码中的 m 个去对某样物体进行称重。在称重时还有额外要求：砝码必须从前往后取，且相邻两个砝码质量不能超过 k，请问有几种挑选方案？

输入格式

输入共 2 行：
第1行：一共3个空格隔开的正整数，依次为 n, m, k；
第2行：一共n个空格隔开的正整数，依次为每一个砝码的重量 wi​。

输出格式

输出共1行：
第1行：为满足题意的方案总数x。

#include <iostream>
using namespace std;

int n, m, k, cnt = 0, a1[35], a2[35];

void dfs(int step, int last)
{
	if (step > m)
	{
		cnt++;
		return;
	}
	
	for (int i = last + 1; i <= n; i++)
	{
		if(a2[i] + a2[last] <= k)
		{
			a1[step] = i;
			dfs(step + 1, i);
		}
	}
}

int main()
{
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a2[i];
	}
	dfs(1, 0);
	cout << cnt << endl;
	return 0;
}

称重2

题目描述

现有n个砝码，第i个砝码的重量为 wi​，我们需要时使用这些砝码中的 m 个去对某样物体进行称重。在称重时还有额外要求：砝码必须从前往后取，且相邻三个砝码质量不能小于k，请问有几种挑选方案？

输入格式

输入共 2 行：
第1行：一共3个空格隔开的正整数，依次为n, m, k；
第2行：一共n个空格隔开的正整数，依次为每一个砝码的重量 wi​。

输出格式

输出共 1行：
第1行：为满足题意的方案总数x。

#include <iostream>
using namespace std;

int n, m, k, cnt = 0, a1[35], a2[35];

void dfs(int step, int last, int last2)
{
	if (step > m)
	{
		cnt++;
		return;
	}
	
	for (int i = last + 1; i <= n; i++)
	{
		if(step <= 2 || a2[i] + a2[last] + a2[last2] >= k)
		{
			a1[step] = i;
			dfs(step + 1, i, last);
		}
	}
}

int main()
{
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a2[i];
	}
	dfs(1, 0, 0);
	cout << cnt << endl;
	return 0;
}