wordpress关于本站,e福州下载app,免费行情软件网站直播,凌晨三点看的片韩国问题关键就是#xff1a; 一个点#xff0c;可能 新开一个组 比 放到已经存在的组 更划算 因为后面的数据#xff0c;我们遍历之前的点时#xff0c;并不知道 所以我们应该针对每个点#xff0c;都应该做出一个选择就是 新开一个元组或者放到之前的元组中#xff0c;都尝…问题关键就是 一个点可能 新开一个组 比 放到已经存在的组 更划算 因为后面的数据我们遍历之前的点时并不知道 所以我们应该针对每个点都应该做出一个选择就是 新开一个元组或者放到之前的元组中都尝试一次(截取重点内容继续往下看)
我们发现这道题目有两个可以剪枝的部分, 一个是如果当前的答案已经大于了我们已知的最小答案,不用说直接return返回即可. 第二个剪枝则是,我们可以将小猫的体重从大到小排序,这样我们的搜索树就会缩短许多,至于为什么,因为我们的剩余空间就变小了,然后可选择的猫也就少了 (截取重点内容继续往下看) 欢迎观看我的博客如有问题交流欢迎评论区留言一定尽快回复大家可以去看我的专栏是所有文章的目录 文章字体风格 红色文字表示重难点★✔ 蓝色文字表示思路以及想法★✔ 如果大家觉得有帮助的话感谢大家帮忙 点赞收藏转发 dfs解决分组问题 分成互质组错误想法从头遍历如果不匹配则开新组正确想法小孩子才做选择dfs直接两种情况都试试 小猫爬山减枝思想 分成互质组 首先什么是互质
互质就是 彼此的最大公约数是 1
求ab的最大公约数
int gcd(int a,int b)
{while(b){int c a % b;a b;b c;}return a;
}错误想法从头遍历如果不匹配则开新组
本题我的想法是 从头遍历如果不匹配则开新组
用样例说就是
6
14 20 33 117 143 175选择20看之前已经开辟的 组别如果已经存在的 组别中的元素
和当前的不符合那么换另一个组别再次尝试
如果都不合适那么直接创建新组错误代码
#includeiostream
#includevectorusing namespace std;const int N 11;int n;
int a[N];
vectorint g[N];int gcd(int a,int b)
{while(b){int c a % b;a b;b c;}return a;
}
int g_size;
void dfs(int u)
{if(un)return;for(int i 1; i g_size; i){int flag 1;for(int j 0; j g[i].size(); j){if(gcd(a[u],g[i][j])!1){flag 0;}}if(flag1){// cout a[u] ;g[i].push_back(a[u]);dfs(u1);return;}}g_size1;g[g_size].push_back(a[u]);dfs(u1);return;
}int main()
{cin n;for(int i 1; i n; i)cin a[i];dfs(1);cout g_size endl;return 0;
}正确想法小孩子才做选择dfs直接两种情况都试试
但是出现问题了
4
3 7 6 14这个样例 安上述思想 分组
3 7
6
14分出3个组 但是
如果按着 正常分组
应该是
3
7 6 14
这样更好问题关键就是 一个点可能 新开一个组 比 放到已经存在的组 更划算 因为后面的数据我们遍历之前的点时并不知道 所以我们应该针对每个点都应该做出一个选择就是 新开一个元组或者放到之前的元组中都尝试一次
//正确代码
#includeiostream
#includevectorusing namespace std;const int N 11;int n;
int a[N];int gcd(int a,int b)
{while(b){int c a % b;a b;b c;}return a;
}
int ans 0x3f3f3f3f;
void dfs(int g_size,vectorint g[N],int u)
{if(un){ans min(g_size,ans);return;}for(int i 1; i g_size; i){int flag 1;for(int j 0; j g[i].size(); j){if(gcd(a[u],g[i][j])!1){flag 0;}}if(flag1){// cout a[u] ;g[i].push_back(a[u]);dfs(g_size,g,u1);g[i].pop_back();}}g[g_size1].push_back(a[u]);dfs(g_size1,g,u1);g[g_size1].pop_back();
}int main()
{cin n;for(int i 1; i n; i)cin a[i];vectorint g[N];dfs(0,g,1);cout ans endl;return 0;
}小猫爬山 减枝思想
本题思路和上题一样 但关键一点是咱们可以借助本题学会剪枝思想 当我们按某一种方案遍历过程时发现走到一半发现这个方案走到了一半已经比我之前走过的方案更费时费力那么就直接不走这个方案了减枝 或者走的过程中按着从大到小 或者从小到大走这样说不定也会省时省力也是减枝 或者就是我们知道了可实现的最坏情况 那么超过可实现的最坏情况一定是不对的直接不需要继续dfs了也是剪枝
我们发现这道题目有两个可以剪枝的部分, 一个是如果当前的答案已经大于了我们已知的最小答案,不用说直接return返回即可. 第二个剪枝则是,我们可以将小猫的体重从大到小排序,这样我们的搜索树就会缩短许多,至于为什么,因为我们的剩余空间就变小了,然后可选择的猫也就少了
/** Project: 0x22_深度优先搜索* File Created:Sunday, January 24th 2021, 11:31:12 am* Author: Bug-Free* Problem:AcWing 165. 小猫爬山*/
#include algorithm
#include iostreamusing namespace std;const int N 2e1;int cat[N], cab[N];
int n, w;
int ans;bool cmp(int a, int b) {return a b;
}void dfs(int now, int cnt) {if (cnt ans) {return;}if (now n 1) {ans min(ans, cnt);return;}//尝试分配到已经租用的缆车上for (int i 1; i cnt; i) { //分配到已租用缆车if (cab[i] cat[now] w) {cab[i] cat[now];dfs(now 1, cnt);cab[i] - cat[now]; //还原}}// 新开一辆缆车cab[cnt 1] cat[now];dfs(now 1, cnt 1);cab[cnt 1] 0;
}int main() {cin n w;for (int i 1; i n; i) {cin cat[i];}sort(cat 1, cat 1 n, cmp);ans n;dfs(1, 0);cout ans endl;return 0;
}
