ZOJ 3681E - Cup 2(记忆化dfs)不好读
https://blog.csdn.net/opm777/article/details/25726221
The European Cup final is coming. The past two World Cup winners, Spain and Italy, will contest the decider at Kiev's Olympic Stadium. Italy-Spain Euro final promises to be clash of polar opposites, so it's difficult to say which team will win.
Now there are M fans in ZJU, N of them support Italy. Suppose you are the president of the students' union and you support Italy. You can divide these M fans into s1 groups(Level 1). More than half of the group(Level 1) support Italy ,than you can say it seems all the M fans support Italy. You can also divide each group(Level 1) into s2 groups(Level 2). More than half of the group(Level 2) support Italy ,than you can say this group(Level 1) support Italy. ... .You can also divide each group(Level i) into s(i+1) groups(Level i+1). More than half of the group(Level i+1) support Italy ,than you can say this group(Level i) support Italy. To be fair, every group(Level i) has the same number of person. Can you find an suitable way to arrange these N person so that all these M fans seem to support Italy.
Input
Mutiple test cases, process to the end of file.
Each case has a single line with two integer M , N (1<=M,N<=100000000).
Output
For each case:
The firt line output Yes if you can do the task or No for not. The second line output the minimum person you need.
Sample Input
4 3 12 5
Sample Output
Yes 3 No 6
假设这n个人所在
比方拆成m组,假设这m组中多于一半是
转载自:left_hand
发现有些情况不能表达。就是
只是開始开数组老是
#include<iostream>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<map>
using namespace std;
//const int maxn=1000005;
//int visi[maxn];
map <int,int> mq;
int dfs(int x)
{
if(mq.count(x)>0)
return mq[x];
int mi=x/2+1;
for(int k=2;k<=sqrt(x+0.5);k++)
{
if(x%k==0)
{
mi=min(mi,(k/2+1)*dfs(x/k));
mi=min(mi,(x/k/2+1)*dfs(k));
}
}
mq[x]=mi;
return mi;
}
int main()
{
int m,n;
while(cin>>m>>n)
{
mq.clear();
//memset(visi,0,sizeof(visi));
int ans=dfs(m);
//int ans=0;
if(ans>n)
printf("No\n%d\n",ans);
else
printf("Yes\n%d\n",ans);
}
return 0;
}
/*
4 3
12 5
*/
相关文章
- UVa572 Oil Deposits DFS求连通块
- 【BZOJ】1673: [Usaco2005 Dec]Scales 天平(dfs背包)
- 【BZOJ】1146: [CTSC2008]网络管理Network(树链剖分+线段树套平衡树+二分 / dfs序+树状数组+主席树)
- POJ 2965 The Pilots Brothers' refrigerator (DFS)
- Uva 10305 - Ordering Tasks 拓扑排序基础水题 队列和dfs实现
- 利用dfs深度遍历
- hdu1978How many ways (记忆化搜索+DFS)
- HDU 4414 Finding crosses (DFS + BFS)
- poj1088-滑雪 【dfs 记忆化搜索】
- LeetCode_DFS_中等_695.岛屿的最大面积
- 【数据结构与算法】图遍历算法 ( 深度优先搜索 DFS | 深度优先搜索和广度优先搜索 | 深度优先搜索基本思想 | 深度优先搜索算法步骤 | 深度优先搜索理论示例 )
- 备赛蓝桥----DFS篇
- 【luogu P1330】封锁阳光大学(dfs)(二分图)(图论)