洛谷P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteins

本文主要是介绍洛谷P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteins，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门：https://www.luogu.com.cn/problem/P1460

写这道题题解是因为对于我对题目的理解是对的，思路也比较清晰。但是在DFS代码的技巧上有欠缺导致无法写出完全AC的代码。从题解中我对DFS函数定义的参数列表有了进一步的了解，在DFS算法中，对与参数列表的定义也是极为重要的，有技巧性地定义参数列表可以减小代码的复杂度，也让写题思路更加清晰。

同时，对与DFS的标记访问和去除标记也清晰了一些，比第一天刚开始摸索时不知道从何下手进步了不少，继续加油！

言归正传。这道题目还是一个两路搜索，对于每种饲料，都可以选择加或者不加。同时还需要设置visit数组来保存访问路径。每访问后需要对此时的状态进行判定，是否满足条件，满足条件则返回并对比答案来确定是否要更新答案，不满足条件继续向下搜索。

上代码，注释写得还算详细。

#include<iostream>
using namespace std;
int Vitamin[30][30] = { 0 }, Need[30] = { 0 };
//两个数组分别是饲料各维他命含量，牛所需维他命量
int visit[30] = { 0 }, Anvisit[30] = { 0 }, ans = 5000;
//visit用来存放当前饲料编号，Anvisit存放答案的饲料编号
//ans存放答案数量，初始值为一个比较大的数
int v = 0, g = 0;
//v,g含义题目中有，不赘述
bool Judge(int amount)
{
	//该函数用来判断当前情况下是否已满足需求
	//amount是已投喂的饲料总数
	if (!amount)return false;
	//如果一种饲料都没加直接pass
	for (int i = 1; i <= v; i++)
	{
		int sum = 0;
		for (int j = 1; j <= amount; j++)
			sum += Vitamin[visit[j]][i];
		//累加，算出每种维生素的含量
		if (sum < Need[i])return false;
		//一旦出现有一种含量小于需求的直接false
	}
	return true;
}
void DFS(int number,int count)
{
	//number为饲料编号，count为饲料总数
	//这样设置参数可以很大程度上避免思考得过于复杂
	if (number > g)
		return;
	//边界
	if (Judge(count)) {//如果满足条件
		if (count < ans) {//并且新答案比原答案小
			ans = count;
			for (int i = 1; i <= count; i++)
				Anvisit[i] = visit[i];
			//更新答案
		}
		return;
		//使命完成，直接返回，不需要再向下执行
	}
	visit[count + 1] = number + 1;
	//准备访问，先打标记
	DFS(number + 1, count + 1);
	//访问下一种饲料并加入
	visit[count + 1] = 0;
	//访问结束，消除标记
	DFS(number + 1, count);
	//访问下一种饲料但不加入
}
int main(void)
{
	scanf("%d", &v);
	for (int i = 1; i <= v; i++)
		scanf("%d", &Need[i]);
	scanf("%d", &g);
	for (int i = 1; i <= g; i++)
		for (int j = 1; j <= v; j++)
			scanf("%d", &Vitamin[i][j]);
	//一堆输入
	DFS(0, 0);
	//注意从编号零开始搜索，因为编号一也要搜索加或者不加两条路
	printf("%d", ans);
	for (int i = 1; i <= ans; i++)
		printf(" %d", Anvisit[i]);
	return 0;//完结撒花
}

这篇关于洛谷P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteins的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！