UVA 10626 Buying Coke (记忆化）
发布时间：2020-12-13 20:16:31 所属栏目：PHP教程 来源：网络整理
导读：地址： 点击打开链接 题意：就是买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分的
|
地址：点击打开链接 题意：就是买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,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,x2⑵,x3)+2);
if(x1>=8) res=min(res,x1⑻,x3)+8);
if(x1>=3&&x3>=1) res=min(res,x1⑶,x2+1,x3⑴)+4);
if(x1>=3&&x2>=1) res=min(res,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,n3));
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |