题意大概是一个自动售货机，然后你有1元，5元，10元三种面值的硬币去买8元一罐的可乐，问你最少投的的硬币数目。可乐只能一罐一罐买，每买一罐机器都会给你找零（eg：一枚10元买一罐可乐得到3枚1元找零）。数据量为1 <= 可乐数 <= 150, 0 <= n1 <= 500, 0 <= n5 <= 100 and 0 <= n10 <= 50.
我最先能想到的是开一个思维数组递推，但是显然会超时。于是就考虑能不能优化掉一维，在最初是考虑可不可以利用贪心先用完其中的一种面值然后再将剩下来的dp，显然这是一个错误的思想。
正确做法是利用记忆化搜索，应为对于每种币值的组合我们都可以算出总和再根据和原有钱的差价就能知道已经买了几罐可乐。所以根据这个可以减去一维，再利用记忆化搜索算出答案。代码如下：
1 #include2 #include 3 #include 4 #define INF 0x7fffffff 5 using namespace std; 6 7 int T, mon[3], c, f[1000][200][100], vis[1000][200][100]; 8 9 int dp(int x, int one, int five, int ten)10 {11 if(vis[one][five][ten]==1) return f[one][five][ten];12 vis[one][five][ten] = 1;13 if(x==0) return f[one][five][ten] = 0;14 int ret = INF;15 if(ten>=1) ret = min(ret, dp(x-1, one+2, five, ten-1)+1);16 if(ten>=1 && one>=3) ret = min(ret, dp(x-1, one-3, five+1, ten-1)+4);17 if(five>=2) ret = min(ret, dp(x-1, one+2, five-2, ten)+2);18 if(five>=1 && one>=3) ret = min(ret, dp(x-1, one-3, five-1, ten)+4);19 if(one>=8) ret = min(ret, dp(x-1, one-8, five, ten)+8);20 return f[one][five][ten] = ret;21 }22 23 int main()24 {25 //freopen("in.txt" ,"r", stdin);26 //freopen("out.txt", "w", stdout);27 28 scanf("%d", &T);29 while(T--){30 memset(mon, 0, sizeof mon);31 memset(vis, 0, sizeof vis);32 memset(f, 0, sizeof f);33 scanf("%d", &c);34 for(int i=0; i<3; i++)35 scanf("%d", &mon[i]);36 printf("%d\n", dp(c, mon[0], mon[1], mon[2]));37 }38 return 0;39 }