程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> UVA 10626 Buying Coke (記憶化)

UVA 10626 Buying Coke (記憶化)

編輯:關於C++

地址:點擊打開鏈接

題意:就是買一個售價8分的飲料,然後你有的硬幣有1,5,10分三種。

然後問買c瓶飲料,一次一次買,你最小的投幣次數。

我們可以有幾種方法:1:投8個一分 2:投一個5分的3個1分的

3:投一個10分的找3個一分的 4:投一個10分的3個一分的,找一個5分的

還有其他方案但是不是太劃算。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 pairpil;
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!=-1)  return res;
    res=INF;
    if(x3>=1)  res=min(res,dfs(num-1,x1+2,x2,x3-1)+1);
    if(x2>=2)  res=min(res,dfs(num-1,x1+2,x2-2,x3)+2);
    if(x1>=8)  res=min(res,dfs(num-1,x1-8,x2,x3)+8);
    if(x1>=3&&x3>=1)  res=min(res,dfs(num-1,x1-3,x2+1,x3-1)+4);
    if(x1>=3&&x2>=1)  res=min(res,dfs(num-1,x1-3,x2-1,x3)+4);
    return res;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&c,&n1,&n2,&n3);
        CLEAR(dp,-1);
        printf("%d\n",dfs(c,n1,n2,n3));
    }
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved