地址：点击打开链接
题意：就是买一个售价8分的饮料，然后你有的硬币有1,5,10分三种。
然后问买c瓶饮料，一次一次买，你最小的投币次数。
我们可以有几种方法：1：投8个一分 2：投一个5分的3个1分的
3：投一个10分的找3个一分的 4：投一个10分的3个一分的，，找一个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!=-1) return res;res=INF;if(x3>=1) res=min(res,dfs(num-1,×1+2,×2,x3-1)+1);if(x2>=2) res=min(res,dfs(num-1,×1+2,×2-2,×3)+2);if(x1>=8) res=min(res,dfs(num-1,×1-8,×2,x3)+8);if(x1>=3&&x3>=1) res=min(res,dfs(num-1,×1-3,×2+1,×3-1)+4);if(x1>=3&&x2>=1) res=min(res,dfs(num-1,×1-3,×2-1,×3)+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;}
人情似纸张张薄，世事如棋局局新。
