背景

又是一道水题

描述

在某个神秘的星球上有一种货币,它有一种奇怪的兑换规则 你有且仅有一枚面值为n的金币，你可以去银行进行兑换，也可以不兑换 如果去银行兑换，兑换的规则是这样的：用面值为a的金币去兑换可以换到a/2,a/3,a/4这三枚硬币（如果 是小数则截尾取整），你可以兑换多次 读入n 输出你最后最多能拥有的钱数w 每个测试点中有T组数据

格式

输入格式

一个数T表示该点的测试数据组数（1=<T<=20 ） 下面跟着T行，每行一个整数n（0 <= n <= 1000000000 ）

输出格式

输出T行(一一对应) 每行一个整数就是你最后最多拥有的钱数w

样例1

样例输入1

2 12 2

样例输出1

13 2

限制

各个测试点3s

提示

小心数据较大，但是不需要高精度

来源

源于spoj

思路 

记忆化搜索 因为最大到10^9 所以数组肯定是不够开的 

这个时候就要 hash优化了

首先 朴素解法只过一个点 20分

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #include<iostream> #define N 10000000 #define ll long long using namespace std; int f[N]; ll dfs(int x){ if(f[x]) return f[x]; int t=dfs(x/2)+dfs(x/3)+dfs(x/4); return f[x]=t>x?t:x; } int main(){ for(int i=0;i<=8;i++) f[i]=i; int T; scanf("%d",&T); int n; while(T--) scanf("%d",&n),printf("%lld\n",dfs(n)); return 0; } hash优化 说明详细见 上一篇博客 传送

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #include<malloc.h> #define M 10017 #define ll long long using namespace std; struct node{ int s; ll v; struct node *next; }*a[M]; ll dfs(ll x){ struct node *p; p=a[x%M]; while(p!=NULL){ int k=p->s; if(k==x) return p->v; p=p->next; } ll ans; if(x<=11) ans=x; else { ll t=dfs(x/2)+dfs(x/3)+dfs(x/4); if(x<t) ans=t;else ans=x; } struct node *q; q=(struct node*)malloc(sizeof(struct node)); q->s=x; q->v=ans; q->next=a[x%M]; a[x%M]=q; return ans; } int main(){ int T,n; scanf("%d",&T); while(T--){ scanf("%d",&n); printf("%lld\n",dfs(n)); } return 0; }