nyoj1270 care for China记忆化搜索-白红宇

nyoj1270 care for China记忆化搜索

阅读量：1870 次

发布时间：2019-04-26

本文共 942 字，大约阅读时间需要 3 分钟。

nyoj1270 care for China

时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
瓷器（china）国为了应对当前经济问题，要推出一套新的经济制度，为什么要推行呢？到底好不好我也不知道（good or bad？），我只知道规则如下：
1：该国家只给人们硬币(还有软妹币，但是软妹币需要用硬币换，有意思？who care)，硬币上有个数字代表该硬币的简直，但是不能直接消费，需要换成软妹币
2：一个硬币可以兑换成3种硬币，n/2，n/3，n/4。（比如12的硬币可以换6+4+3=13价值的硬币）
3：价值为x的硬币也可以换成x软妹币
那么问题来了，假如你有一个价值为n的硬币，你可以换成多少软妹币？
输入
多组输入
每组一个数字n（0<=n<=1000000000）,这个数字就写在你的硬币上面
输出
每组输入输出一行，表示你可以换得的软妹币的价值，请最大化这个数，谢谢
样例输入
12
样例输出
13

#include
   
    #include
    #include
     
      using namespace std;map
      
        m;long long DFS(long long n);int main() {  long long n;  for (long long i = 0; i <= 11; i++) m[i] = i;  while (scanf("%lld", &n) != EOF) {    printf("%lld\n", DFS(n));  }  return 0;}long long DFS(long long n) {
  //记忆化搜索   if (m.find(n) == m.end()) {    long long temp = DFS(n / 2) + DFS(n / 3) + DFS(n / 4);    if (temp > n) {      m[n] = temp;      return m[n];    }else {      m[n] = n;      return m[n];    }  }else return m[n];}

转载地址：http://yzeff.baihongyu.com/

你可能感兴趣的文章

JVM Minor GC、Full GC和Major GC

查看>>

SpringBoot @Scheduled 执行两次的问题

查看>>