Uva-10626 Buying Coke DP+记忆化搜索

本文主要是介绍Uva-10626 Buying Coke DP+记忆化搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

状态： dp[a][b][c]表示1块的a个5快的b个10块的c个的投币数

#include <stdio.h>
#include <string.h>
#include <iostream>
#include<functional>
#include <queue>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 106;
const int inf = 1<<30;
int n;
int dp[705][105][55];            //注意数组要开大点 因为有找钱
int Dp( int a,int b,int c,int x )
{if( !x )	return 0;if( dp[a][b][c] != -1 )	return dp[a][b][c];dp[a][b][c] = inf;if( c >= 1 )dp[a][b][c] = min( dp[a][b][c],Dp(a+2,b,c-1,x-1) + 1 );if( c >= 1 && a >= 3 )dp[a][b][c] = min( dp[a][b][c],Dp(a-3,b+1,c-1,x-1) + 4 );if( b >= 2 )dp[a][b][c] = min( dp[a][b][c],Dp(a+2,b-2,c,x-1) + 2 );if( b >= 1 && a >= 3 )dp[a][b][c] = min( dp[a][b][c],Dp(a-3,b-1,c,x-1) + 4 );if( a >= 8 )dp[a][b][c] = min( dp[a][b][c],Dp(a-8,b,c,x-1) + 8 );return dp[a][b][c];
}
int main()
{#ifndef ONLINE_JUDGE  freopen("data.txt","r",stdin);  #endif int cas,a,b,c;;scanf("%d",&cas);while( cas -- ){int ans = 0;scanf("%d",&n);scanf("%d%d%d",&a,&b,&c);memset( dp,-1,sizeof(dp) );printf("%d\n",Dp( a,b,c,n ));}return 0;
}

这篇关于Uva-10626 Buying Coke DP+记忆化搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---