40 条题解
-
0
how LV 10 @ 2009-07-30 21:59:09
...多谢fengyuchen牛指点..让我成功升为2星...~~
-
0
w122185976q LV 9 @ 2009-07-30 15:11:17
搜索会不会超啊?
占个位子先! -
0
fengyuchen LV 10 @ 2009-07-30 14:22:51
我来了
-
0
JackDavid127 LV 10 @ 2009-07-30 13:00:59
很神秘的题目……
-
0
fammiebright LV 9 @ 2009-07-30 12:51:37
-_-|||
欢迎访问个人blog http://dfs35123.spaces.live.com/ -
-1
map大法好！！！
```
//
//Problem:Vijos P1599 货币
//Writer:LZX
//Algorithm:记忆化搜索
//Date:2016.2.16
//
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;#define next nextx
map<int,long long>dfsx;
int t;inline int read(){
int x=0,fu=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')fu=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*fu;
}inline long long dfs(int x){
if(x==0)return 0;
if(dfsx[x])return dfsx[x];
long long dfsxx=dfs(x/2)+dfs(x/3)+dfs(x/4);
return dfsx[x]=(dfsxx>x)?dfsxx:x;
}int main(){
t=read();
for(int i=1;i<=t;i++){
int x=read();
printf("%lld\n",dfs(x));
}
return 0;
}
```测试数据 #0: Accepted, time = 0 ms, mem = 272 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 276 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 280 KiB, score = 20
测试数据 #3: Accepted, time = 0 ms, mem = 308 KiB, score = 20
测试数据 #4: Accepted, time = 0 ms, mem = 308 KiB, score = 20
Accepted, time = 0 ms, mem = 308 KiB, score = 100 -
-1
#include<cstdio>
#include<cstring>
using namespace std;
long long a[40000001];
long long mymax(long long x,long long y){return x>y?x:y;}
long long dfs(long long x)
{
if(x<3) return x;
if(x<40000001 && a[x]!=0) return a[x];
if(x<40000001) return a[x]=mymax(x,dfs(x/2)+dfs(x/4)+dfs(x/3));
else return mymax(x,dfs(x/2)+dfs(x/4)+dfs(x/3));
}
int main()
{
long long n;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%I64d",&n);
printf("%I64d\n",dfs(n));
}
return 0;
} -
-2
编译通过...
├ 测试数据 01：答案正确... 41ms
├ 测试数据 02：答案正确... 9ms
├ 测试数据 03：答案正确... 41ms
├ 测试数据 04：答案正确... 25ms
├ 测试数据 05：答案正确... 41ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：157ms
先计算一个1000万的表（小数据时可能不兑换，大数据一定兑换），再开始读数据。
表内有的直接出表内没有的dfs：
function find(x:int64):int64;
begin
if x
how
LV 10
@ 2009-07-30 21:59:09
