C++ 动态规划解决商场购物支付验证问题

///'使用动态规划来解决这个问题。//n//n首先定义一个二维数组dp，dp[i][j]表示使用前i张纸币时，面值为j的纸币的最小验证时间和。//n//n初始化dp数组为无穷大，即dp[i][j] = INF。//n//n然后对于每一种面值的纸币，遍历使用的张数k（k从1到n），更新dp数组。假设当前考虑的是面值为A的纸币，那么对于使用k张面值为A的纸币时，有以下两种情况：//n1. 不使用面值为A的纸币，即dp[i][j] = dp[i][j]，此时验证时间不变。//n2. 使用k张面值为A的纸币，即dp[i][j] = dp[i-k][j-A] + k * Y，此时验证时间为前i-k张纸币的验证时间和加上k张面值为A的纸币的验证时间。//n//n在更新dp数组时，可以取上述两种情况中的较小值。//n//n最后的答案就是dp[n][1]，即使用n张纸币时，面值为1的纸币的最小验证时间和。//n//n以下是C++代码实现：//n//ncpp//n#include <iostream>//n#include <algorithm>//nusing namespace std;//n//nconst int MAXN = 1005;//nconst int INF = 1e9;//n//nint main() {//n int n, X, A, Y, B, Z;//n cin >> n >> X >> A >> Y >> B >> Z;//n//n int dp[MAXN][MAXN];//n for (int i = 0; i <= n; i++) {//n for (int j = 0; j <= n; j++) {//n dp[i][j] = INF;//n }//n }//n dp[0][0] = 0;//n//n for (int i = 1; i <= n; i++) {//n for (int j = 0; j <= n; j++) {//n dp[i][j] = min(dp[i][j], dp[i-1][j]);//n if (j >= A) {//n dp[i][j] = min(dp[i][j], dp[i-1][j-A] + Y);//n }//n if (j >= B) {//n dp[i][j] = min(dp[i][j], dp[i-1][j-B] + Z);//n }//n }//n }//n//n int ans = INF;//n for (int i = 0; i <= n; i++) {//n ans = min(ans, dp[n][i]);//n }//n//n cout << ans + n * X << endl;//n//n return 0;//n}//n//n//n输入样例：//n5 1 2 3 4 5//n//n输出样例：//n14//n//n/