C++ 算法：使用动态规划求解最小的验证时间

\u007b"title":"C++ \u52a8\u6001\u89c4\u5212\uff1a\u4f7f\u7528\u52a8\u6001\u89c4\u5212\u6c42\u89e3\u6700\u5c0f\u7684\u9a8c\u8bc1\u65f6\u95f4","description":"\u672c\u7bc7\u4ecb\u7ecd\u4f7f\u7528\u52a8\u6001\u89c4\u5212\u7b97\u6cd5\u89e3\u51b3\u652f\u4ed8\u95ee\u9898\uff0c\u6c42\u89e3\u4f7f\u7528\u4e09\u79cd\u9762\u503c\u7eb8\u5e01\u652f\u4ed8\u6240\u9700\u7684\u6700\u77ed\u9a8c\u8bc1\u65f6\u95f4\u3002\u6587\u4e2d\u5305\u542b\u4e2d\u5305\u542bC++\u4ee3\u7801\u793a\u4f8b\uff0c\u5e76\u63d0\u4f9b\u8f93\u5165\u548c\u8f93\u51fa\u793a\u4f8b\uff0c\u65b9\u4fbf\u8bfb\u8005\u7406\u89e3\u3002","keywords":"\u52a8\u6001\u89c4\u5212\uff0c C++, \u9a8c\u8bc1\u65f6\u95f4\uff0c \u652f\u4ed8\u65b9\u6848\uff0c \u7b97\u6cd5\uff0c \u4ee3\u7801\u793a\u4f8b","content":"\u8fd9\u4e2a\u95ee\u9898\u53ef\u4ee5\u4f7f\u7528\u52a8\u6001\u89c4\u5212\u6765\u89e3\u51b3\u3002\u9996\u5148\u5b9a\u4e49\u4e00\u7ef4\u6570\u7ec4dp\uff0c\u5176\u4e2d\u0064\u0070\u005b\u0069\u005d\u8868\u793a\u652f\u4ed8\u603b\u989d\u4e3a\u0069\u65f6\u7684\u6700\u5c0f\u9a8c\u8bc1\u65f6\u95f4\u3002\u521d\u59cb\u65f6\uff0c\u5c06\u0064\u0070\u6570\u7ec4\u7684\u6240\u6709\u5143\u7d20\u90fd\u8bbe\u5b9a\u4e3a\u65e0\u7ea6\u5927\uff0c\u8868\u793a\u4e0d\u53ef\u80fd\u8fbe\u5230\u8be5\u652f\u4ed8\u603b\u989d\u3002\u7136\u540e\uff0c\u901a\u8fc7\u4ece1\u5230\u76ee\u6807\u652f\u4ed8\u603b\u989d\u7684\u6240\u6709\u91d1\u989d\uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u91d1\u989d\u0069\uff0c\u901a\u8fc7\u7eb8\u5e01\u7684\u9762\u503c\uff0c\u8ba1\u7b97\u4f7f\u7528\u5f53\u524d\u9762\u503c\u7684\u7eb8\u5e01\u652f\u4ed8\u91d1\u989d\u0069\u6240\u9700\u7684\u9a8c\u8bc1\u65f6\u95f4\uff0c\u5e76\u66f4\u65b0\u0064\u0070\u005b\u0069\u005d\u4e3a\u5f53\u524d\u9762\u503c\u7eb8\u5e01\u7684\u9a8c\u8bc1\u65f6\u95f4\u548c\u0064\u0070\u005b\u0069\u002d\u9762\u503c\u005d\u7684\u6bd4\u8f83\u5c0f\u503c\u3002\u6700\u540e\uff0c\u8f93\u51fa\u0064\u0070\u005b\u76ee\u6807\u652f\u4ed8\u603b\u989d\u005d\u5c31\u662f\u6700\u5c0f\u7684\u9a8c\u8bc1\u65f6\u95f4\u3002\n\n\u5177\u4f53\u7684C++\u4ee3\u7801\u5982\u4e0b\uff1a\n\n\u0060\u0060\u0060cpp\n#include \u003ciostream\u003e\n#include \u003cvector\u003e\n#include \u003calgorithm\u003e\n#include \u003cclimits\u003e\nusing namespace std;\n\nint main() \u007b\n int target, n;\n int X, Y, Z;\n int A, B;\n cin >> target >> n >> X >> Y >> Z >> A >> B;\n\n vector\u003cint\u003e dp(target + 1, INT_MAX);\n dp[0] = 0;\n\n for (int i = 1; i <= target; i++) \u007b\n if (i >= 1) \u007b\n dp[i] = min(dp[i], dp[i - 1] + X);\n \u007d\n if (i >= A) \u007b\n dp[i] = min(dp[i], dp[i - A] + Y);\n \u007d\n if (i >= B) \u007b\n dp[i] = min(dp[i], dp[i - B] + Z);\n \u007d\n \u007d\n\n cout << dp[target] << endl;\n\n return 0;\n\u007d\n\u0060\u0060\u0060\n\n\u8f93\u5165\u793a\u4f8b\uff1a\n\u0060\u0060\u0060\n10 3 2 3 4 1 2\n\u0060\u0060\u0060\n\n\u8f93\u51fa\u793a\u4f8b\uff1a\n\u0060\u0060\u0060\n8\n\u0060\u0060\u0060\n\n\u8bf4\u660e\uff1a\n\u652f\u4ed8\u603b\u989d\u4e3a10\uff0c\u7eb8\u5e01\u9762\u503c\u5206\u522b\u4e3a1\u30012\u30013\uff0c\u9a8c\u8bc1\u65f6\u95f4\u5206\u522b\u4e3a2\u30013\u30014\uff0c\u4f7f\u7528\u7eb8\u5e01\u9762\u503c\u4e3a1\u7684\u7eb8\u5e01\u652f\u4ed810\u9700\u898125=10\u7684\u9a8c\u8bc1\u65f6\u95f4\uff0c\u4f7f\u7528\u7eb8\u5e01\u9762\u503c\u4e3a2\u7684\u7eb8\u5e01\u652f\u4ed810\u9700\u898135=15\u7684\u9a8c\u8bc1\u65f6\u95f4\uff0c\u4f7f\u7528\u7eb8\u5e01\u9762\u503c\u4e3a3\u7684\u7eb8\u5e01\u652f\u4ed810\u9700\u89814*3=12\u7684\u9a8c\u8bc1\u65f6\u95f4\u3002\u6240\u4ee5\u6700\u5c0f\u7684\u9a8c\u8bc1\u65f6\u95f4\u4e3a8\u3002