当前位置:网站首页>Luogu p1460 [usaco2.1] healthy Holstein cows
Luogu p1460 [usaco2.1] healthy Holstein cows
2022-07-06 05:59:00 【Study_ Study_ X】
Portal :https://www.luogu.com.cn/problem/P1460
I wrote this problem solution because my understanding of the problem is right , The thinking is clear . But in DFS There is a lack of skill in the code, which makes it impossible to write completely AC Code for . From the solution to the question, I am right DFS The parameter list of function definition has been further understood , stay DFS In the algorithm, , The definition of parameter list is also extremely important , Defining parameter lists skillfully can reduce the complexity of code , It also makes the idea of writing questions clearer .
meanwhile , To and DFS Tag access and tag removal are also clearer , It's a lot better than the first day when I didn't know where to start , Continue refueling !
Get down to business . This topic is still a two-way search , For each feed , You can choose to add or not . It also needs to be set visit Array to save the access path . After each visit, the status at this time needs to be determined , Whether the conditions are met , If the conditions are met, return and compare the answers to determine whether to update the answers , If the conditions are not met, continue to search downward .
Code up , The notes are fairly detailed .
#include<iostream>
using namespace std;
int Vitamin[30][30] = { 0 }, Need[30] = { 0 };
// The two arrays are the vitamin content of feed , Vitamins needed by cattle
int visit[30] = { 0 }, Anvisit[30] = { 0 }, ans = 5000;
//visit Used to store the current feed number ,Anvisit Feed number for storing answers
//ans Store the number of answers , The initial value is a relatively large number
int v = 0, g = 0;
//v,g Meaning the title has , Don't go into
bool Judge(int amount)
{
// This function is used to judge whether the requirements have been met in the current situation
//amount Is the total amount of feed that has been fed
if (!amount)return false;
// If one kind of feed is not added directly pass
for (int i = 1; i <= v; i++)
{
int sum = 0;
for (int j = 1; j <= amount; j++)
sum += Vitamin[visit[j]][i];
// Add up , Calculate the content of each vitamin
if (sum < Need[i])return false;
// Once there is a direct false
}
return true;
}
void DFS(int number,int count)
{
//number Number the feed ,count Is the total feed
// Setting parameters in this way can largely avoid thinking too complicated
if (number > g)
return;
// The border
if (Judge(count)) {// If the conditions are met
if (count < ans) {// And the new answer is smaller than the original answer
ans = count;
for (int i = 1; i <= count; i++)
Anvisit[i] = visit[i];
// Update answers
}
return;
// Mission accomplished , Go straight back to , There is no need to go down
}
visit[count + 1] = number + 1;
// Prepare to visit , Mark first
DFS(number + 1, count + 1);
// Visit the next feed and add
visit[count + 1] = 0;
// Access to the end , Eliminate marking
DFS(number + 1, count);
// Visit the next feed without adding
}
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]);
// A bunch of inputs
DFS(0, 0);
// Pay attention to search from zero , Because number one also needs to search for two ways to add or not add
printf("%d", ans);
for (int i = 1; i <= ans; i++)
printf(" %d", Anvisit[i]);
return 0;// End of the flower
}
边栏推荐
- Li Chuang EDA learning notes 12: common PCB board layout constraint principles
- 查询生产订单中某个(些)工作中心对应的标准文本码
- Novice entry SCM must understand those things
- 什么是独立IP,独立IP主机怎么样?
- YYGH-11-定时统计
- 数字经济破浪而来 ,LTD是权益独立的Web3.0网站?
- Garbage collector with serial, throughput priority and response time priority
- 如何在业务代码中使用 ThinkPHP5.1 封装的容器内反射方法
- 华为路由器忘记密码怎么恢复
- ContentType的作用
猜你喜欢
随机推荐
公司视频加速播放
《卓有成效的管理者》读书笔记
Huawei BFD configuration specification
Investment strategy discussion and market scale prediction report of China's solid state high power amplifier industry from 2022 to 2028
IPv6 comprehensive experiment
Analysis of grammar elements in turtle Library
A complete collection of necessary learning websites for office programmers
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Embedded interview questions (IV. common algorithms)
Rustdesk builds its own remote desktop relay server
Demander le Code de texte standard correspondant à un centre de travail dans l'ordre de production
Detailed explanation of BF and KMP
HCIA复习
类和对象(一)this指针详解
Redis message queue
MIT6.s081-2020 Lab2 System Calls
Implementation of linked list in address book management system
Station B Liu Erden linear regression pytoch
查詢生產訂單中某個(些)工作中心對應的標准文本碼
H3C S5820V2_5830V2交换机IRF2堆叠后升级方法