我是靠谱客的博主 美丽帅哥,这篇文章主要介绍洛谷P1460 健康的荷斯坦奶牛,现在分享给大家,希望可以做个参考。

解题思路:
首先想到的是搜索,搜索使用哪几种符合条件的饲料,找最小的花费。由于dfs的特点,先找到的方案一定是字典序最小的。
但是暴力搜索会超时,需要剪枝,详见注释

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m,v[35],a[35][35],ans=1e9,cnt,t,c[35],top[35]; void dfs(int x,int sum){ bool flag=0; for (int i=1;i<=n;i++) if (v[i]>0) {flag=1;break;}//边界条件,要使每个v[i]都<0; if (!flag){ if (sum<ans){//最优性剪枝 ans=sum; t=cnt; for (int i=1;i<=cnt;i++) c[i]=top[i]; } return ; } for (int i=x+1;i<=m;i++){//从x+1搜索,不再搜索前边的,可行性剪枝 for (int j=1;j<=n;j++) v[j]-=a[i][j]; top[++cnt]=i; dfs(i,sum+1); --cnt;//回溯 for (int j=1;j<=n;j++) v[j]+=a[i][j];//回溯 } } int main(){ cin>>n; for (int i=1;i<=n;i++) scanf("%d",&v[i]); cin>>m; for(int i=1;i<=m;i++) for (int j=1;j<=n;j++) scanf("%d",&a[i][j]); dfs(0,0); cout<<t<<" "; for (int i=1;i<=t;i++) cout<<c[i]<<" "; return 0; }

最后

以上就是美丽帅哥最近收集整理的关于洛谷P1460 健康的荷斯坦奶牛的全部内容,更多相关洛谷P1460内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(100)

评论列表共有 0 条评论

立即
投稿
返回
顶部