首页 > 代码库 > 2014 Super Training #9 C E - Cup 2 --记忆化搜索
2014 Super Training #9 C E - Cup 2 --记忆化搜索
原题:ZOJ 3681 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3681
题意:给一个m,n,m表示m个人,可以把m个人分成k组,每组m/k个人,人数要一样,如果超过一半的组支持Italy的话,说明这n个人都支持Italy.同时又可以把这k组中任意一组或多组再继续往下分,假设再把m/k分成p组,如果这p组中有超过一半的组支持Italy的话,说明m/k是支持Italy的,如此类推。给定有n个人支持Italy,问能否使看起来这m个人都支持Italy。并求求最少需要多少人支持Italy,才能确保这m个人都支持Italy.
做法:DFS出使看起来m个人都支持Italy所需的最小人数,然后与n比较,如果res<=n则能达到,否则不能达到。
DFS时,枚举其约数(因为要分成人数相等的组),然后分下去再DFS。
代码:
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>#include <map>using namespace std;#define N 1007std::map<int, int> ans;int DFS(int m){ if(ans.count(m)) return ans[m]; int mini = m/2+1; for(int i=2;i*i<=m;i++) { if(m%i == 0) { mini = min(mini,((m/i)/2+1)*DFS(i)); mini = min(mini,(i/2+1)*DFS(m/i)); } } ans[m] = mini; return ans[m];}int main(){ int n,m; ans.clear(); while(scanf("%d%d",&m,&n)!=EOF) { int res = DFS(m); if(res <= n) puts("Yes"); else puts("No"); printf("%d\n",res); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。