首页 > 代码库 > 2014 Super Training #9 C E - Cup 2 --记忆化搜索

2014 Super Training #9 C E - Cup 2 --记忆化搜索

2024-07-11 17:08:54   222人阅读

原题：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;}
View Code

 


联系
我们