此题状态即为各种硬币个数，然后分类讨论即可。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int t; int num, n[3], dp[705][220][100], vis[705][220][100]; int dfs(int num, int n1, int n2, int n3) { int &sum = dp[n1][n2][n3]; int &flag = vis[n1][n2][n3]; if (flag) return sum; else if (num == 0) { flag = 1; sum = 0; return sum; } else { sum = 2000000000; if (n1 >= 8) sum = min(sum, dfs(num - 1, n1 - 8, n2, n3) + 8); if (n2 >= 1 && n1 >= 3) sum = min(sum, dfs(num - 1, n1 - 3, n2 - 1, n3) + 4); if (n3 >= 1 && n1 >= 3) sum = min(sum, dfs(num - 1, n1 - 3, n2 + 1, n3 - 1) + 4); if (n2 >= 2) sum = min(sum, dfs(num - 1, n1 + 2, n2 - 2, n3) + 2); if (n3 >= 1) sum = min(sum, dfs(num - 1, n1 + 2, n2, n3 - 1) + 1); flag = 1; return sum; } } int main() { scanf("%d", &t); while (t --) { memset(vis, 0, sizeof(vis)); scanf("%d", &num); for (int i = 0; i < 3; i ++) scanf("%d", &n[i]); printf("%d ", dfs(num, n[0], n[1], n[2])); } return 0; }