程序员人生 网站导航

UVA 10626 Buying Coke (记忆化)

栏目:php教程时间:2015-03-19 08:09:04

地址:点击打开链接

题意:就是买1个售价8分的饮料,然后你有的硬币有1,5,10分3种。

然后问买c瓶饮料,1次1次买,你最小的投币次数。

我们可以有几种方法:1:投8个1分  2:投1个5分的3个1分的

3:投1个10分的找3个1分的 4:投1个10分的3个1分的,找1个5分的

还有其他方案但是否是太划算。

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<string> #include<iostream> #include<queue> #include<cmath> #include<map> #include<stack> #include<bitset> using namespace std; #define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define CLEAR( a , x ) memset ( a , x , sizeof a ) typedef long long LL; typedef pair<int,int>pil; const int INF = 0x3f3f3f3f; const int maxn=1100; char str[maxn]; int dp[1100][155][55]; int n1,n2,n3,c; int dfs(int num,int x1,int x2,int x3)//num,1,5,10 { if(num==0) return 0; int &res=dp[x1][x2][x3]; if(res!=⑴) return res; res=INF; if(x3>=1) res=min(res,dfs(num⑴,x1+2,x2,x3⑴)+1); if(x2>=2) res=min(res,dfs(num⑴,x1+2,x2⑵,x3)+2); if(x1>=8) res=min(res,dfs(num⑴,x1⑻,x2,x3)+8); if(x1>=3&&x3>=1) res=min(res,dfs(num⑴,x1⑶,x2+1,x3⑴)+4); if(x1>=3&&x2>=1) res=min(res,dfs(num⑴,x1⑶,x2⑴,x3)+4); return res; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d%d%d",&c,&n1,&n2,&n3); CLEAR(dp,⑴); printf("%d ",dfs(c,n1,n2,n3)); } return 0; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐