{"id":333,"date":"2019-10-07T15:43:52","date_gmt":"2019-10-07T07:43:52","guid":{"rendered":"http:\/\/www.guanhaobo.cn\/?p=333"},"modified":"2019-10-07T15:43:52","modified_gmt":"2019-10-07T07:43:52","slug":"bjtuoj-1844-hwf%e5%90%83%e6%8a%ab%e8%90%a8","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=333","title":{"rendered":"BJTUOJ 1844 \u2014 hwf\u5403\u62ab\u8428"},"content":{"rendered":"

\u63cf\u8ff0<\/h3>\n

hwf \u662f\u4e00\u4e2a\u975e\u5e38\u559c\u6b22\u5403\u62ab\u8428\u7684\u4eba\u3002\u67d0\u5929\uff0c\u5929\u4e0a\u6389\u4e0b\u4e86\u4e00\u5f20\u62ab\u8428\uff0c\u88ab hwf \u548c\u9ad8\u8001\u5e08\u770b\u5230\u4e86\u3002<\/p>\n

\u9ad8\u8001\u5e08\u628a\u62ab\u8428\u5206\u6210\u4e86 n \u4efd, \u7b2c i \u4efd\u7684\u89d2\u5ea6\u4e3a ai\u3002\u4e3a\u4e86\u516c\u5e73\u8d77\u89c1\uff0c\u4ed6\u4eec\u51b3\u5b9a\u7531 hwf \u628a n \u4efd\u62ab\u8428\u5206\u6210\u4e24\u5806\uff0c\u7136\u540e\u9ad8\u8001\u5e08\u80af\u5b9a\u4f1a\u6311\u4e00\u5806\u89d2\u5ea6\u548c\u591a\u7684\uff0chwf \u62ff\u5269\u4e0b\u7684\u4e00\u5806\u3002hwf \u60f3\u5403\u5230\u5c3d\u53ef\u80fd\u591a\u7684\u62ab\u8428\uff0c\u4f46\u662f hwf \u7684\u5fc3\u601d\u5df2\u7ecf\u5168\u5728\u5403\u62ab\u8428\u4e0a\u4e86\u3002<\/p>\n

\u5feb\u5e2e\u52a9 hwf\uff0c\u544a\u8bc9\u4ed6\u6700\u591a\u80fd\u5403\u5230\u591a\u5c11\u62ab\u8428\u5427\uff01<\/p>\n

\u9898\u76ee\u94fe\u63a5<\/h3>\n

https:\/\/citel.bjtu.edu.cn\/acm\/problem\/1844<\/a><\/p>\n

\u8f93\u5165\u6570\u636e<\/h3>\n

\u7b2c\u4e00\u884c\u4e3a\u4e00\u4e2a\u6574\u6570 t (1\u2264t\u2264500)\uff0c\u8868\u793a\u6570\u636e\u7684\u7ec4\u6570\u3002\u63a5\u4e0b\u6765\u5bf9\u4e8e\u6bcf\u7ec4\u6570\u636e\uff1a
\n\u7b2c\u4e00\u884c\u6709\u4e00\u4e2a\u6574\u6570 n (2\u2264n\u2264360)\uff0c\u8868\u793a\u62ab\u8428\u88ab\u5206\u6210\u7684\u4efd\u6570\u3002
\n\u7b2c\u4e8c\u884c\u6709 n \u4e2a\u6574\u6570 a1,a2,\u2026,an (1\u2264ai<360)\uff0c\u5206\u522b\u8868\u793a\u7b2c i \u4efd\u62ab\u8428\u7684\u89d2\u5ea6\u3002<\/p>\n

\u4fdd\u8bc1 \u2211ai=360<\/p>\n

\u8f93\u51fa\u6570\u636e<\/h3>\n

\u5bf9\u4e8e\u6bcf\u7ec4\u6570\u636e\uff0c\u8f93\u51fa\u4e00\u884c\uff1a
\n\u7b2c\u4e00\u884c\u4e3a\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793ahwf\u6700\u591a\u53ef\u4ee5\u5403\u5230\u62ab\u8428\u7684\u89d2\u5ea6\u6570\u3002<\/p>\n

\u6837\u4f8b\u8f93\u5165<\/h3>\n
2\n4\n10 130 170 50\n3\n200 60 100\n<\/code><\/pre>\n
\u6837\u4f8b\u8f93\u51fa<\/h3>\n
180\n160\n<\/code><\/pre>\n
\u9898\u76ee\u5206\u6790<\/h3>\n
n \u6700\u5927\u4e3a360\uff0c\u5982\u679c\u4f7f\u7528\u641c\u7d22\u80af\u5b9a\u4f1a\u8d85\u65f6\u3002
\n\u52a8\u6001\u89c4\u5212\u3002
\n\u9898\u76ee\u53ef\u4ee5\u8f6c\u5316\u4e3a\u5f80\u5bb9\u79ef\u4e3a180\u7684\u7bb1\u5b50\u91cc\u653e\u62ab\u8428\uff0c\u6700\u591a\u80fd\u653e\u591a\u5c11\u62ab\u8428\ud83c\udf55\uff1f
\n\u8bbenum[i]<\/code>\u8868\u793a\u7b2c i \u5757\u62ab\u8428\u7684\u89d2\u5ea6\uff1bres[i][j]<\/code>\u8868\u793a\u5728\u524d i \u5757\u62ab\u8428\u4e2d\u9009\u62e9\u82e5\u5e72\u62ab\u8428\u653e\u5165\u5bb9\u79ef\u4e3a j \u7684\u7bb1\u5b50\u91cc\uff0c\u80fd\u653e\u5165\u7684\u62ab\u8428\u89d2\u5ea6\u548c\u7684\u6700\u5927\u503c\u3002
\nnum[i] > j<\/code>\u65f6\uff0c\u7b2c i \u5757\u62ab\u8428\u4e0d\u80fd\u653e\u5165\u5bb9\u79ef\u4e3a j \u7684\u7bb1\u5b50\u4e2d\uff0c\u6613\u5f97res[i][j] = res[i-1][j]<\/code>
\nnum[i] <= j<\/code>\u65f6\uff0c\u5982\u679c\u7b2c i \u5757\u62ab\u8428\u4e0d\u653e\u5165\u7bb1\u5b50\uff0c\u5219res[i][j] = res[i-1][j]<\/code>\uff1b\u5982\u679c\u7b2c i \u5757\u62ab\u8428\u653e\u5165\u7bb1\u5b50\uff0c\u5219res[i][j] = num[i] + res[i-1][j-num[i]]<\/code>\uff1b\u6240\u4ee5\u6709res[i][j] = max(res[i - 1][j], num[i] + res[i - 1][j - num[i]])<\/code>
\n\u7efc\u4e0a\u6240\u8ff0\uff0c\u6211\u4eec\u5f97\u5230\u4e86\u4e0b\u9762\u7684\u9012\u63a8\u5173\u7cfb\u5f0f<\/p>\n
if (num[i] > j)\n    res[i][j] = res[i - 1][j];\nelse\n    res[i][j] = max(res[i - 1][j], num[i] + res[i - 1][j - num[i]]);\n<\/code><\/pre>\n
\u6211\u4eec\u4f1a\u53d1\u73b0\uff0cres[i][j]<\/code>\u53ea\u548c\u4e0b\u6807\u6bd4\u5b83\u5c0f\u7684res[i - 1][j]<\/code>\u4ee5\u53cares[i - 1][j - num[i]]<\/code>\u6709\u5173\uff0c\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528\u4e24\u5c42\u5faa\u73af\u5c06 res \u6570\u7ec4\u6240\u6709\u7684\u503c\u90fd\u8ba1\u7b97\u51fa\u6765\u3002
\n\u9700\u8981\u5bf9 res \u6570\u7ec4\u8fdb\u884c\u4e00\u4e9b\u521d\u59cb\u5316\u5de5\u4f5c\uff0c\u624d\u80fd\u901a\u8fc7\u9012\u63a8\u6c42\u51fa\u540e\u9762\u7684\u503c\u3002
\nres[n][180]<\/code>\u5c31\u662f\u95ee\u9898\u7684\u7b54\u6848\u3002<\/p>\n
AC\u4ee3\u78011<\/h3>\n
\u4e0a\u9762\u5206\u6790\u4e2d\uff0cres \u7684\u7b2c\u4e00\u7ef4\u4e0b\u6807\u662f\u4ece 1 \u5f00\u59cb\u7684\uff0c\u4ee3\u7801\u4e2d\u7684\u662f\u4ece 0 \u5f00\u59cb\u7684\u3002
\n\u5728\u4ee3\u7801\u4e2d\uff0cres[n-1][180]<\/code>\u662f\u6700\u7ec8\u7b54\u6848\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint main()\n{\n    int num[365], n, t, i, j, res[365][185];\n    cin >> t;\n    while (t--)\n    {\n        memset(res, 0, sizeof(res));\n        cin >> n;\n        for (i = 0; i < n; i++)\n            cin >> num[i];\n        for (j = 180; j >= num[0]; j--)\n            res[0][j] = num[0];\n        for (i = 1; i < n; i++)\n        {\n            for (j = 1; j <= 180; j++)\n            {\n                if (num[i] > j)\n                    res[i][j] = res[i - 1][j];\n                else\n                    res[i][j] = max(res[i - 1][j], num[i] + res[i - 1][j - num[i]]);\n            }\n        }\n        cout << res[n - 1][180] << endl;\n    }\n    return 0;\n}\n<\/code><\/pre>\n
AC\u4ee3\u78012<\/h3>\n
\u5927\u5bb6\u4f1a\u53d1\u73b0\uff0cres[i][j]<\/code>\u5728\u7b2c\u4e00\u7ef4\u5ea6\u4e0a\u53ea\u548cres[i-1]<\/code>\u6709\u5173\u3002
\n\u6240\u4ee5res\u6570\u7ec4\u7684\u7b2c\u4e00\u4e2a\u7ef4\u5ea6\u5176\u5b9e\u53ef\u4ee5\u7701\u7565\u3002
\n\u53e6\u5916\uff0c\u5728j < num[i]<\/code>\u65f6\uff0cres[i][j] = res[i-1][j]<\/code>\uff0c\u5728\u7701\u7565\u4e86\u7b2c\u4e00\u7ef4\u5ea6\u540e\uff0c\u8fd9\u4e2a\u4e5f\u53ef\u4ee5\u4e0d\u5199\u4e86\uff0c\u56e0\u4e3ares[j] = res[j]<\/code><\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint main()\n{\n    int num[365], n, t, i, j, res[185];\n    cin >> t;\n    while (t--)\n    {\n        memset(res, 0, sizeof(res));\n        cin >> n;\n        for (i = 0; i < n; i++)\n            cin >> num[i];\n        for (i = 0; i < n; i++)\n            for (j = 180; j >= num[i]; j--)\n                res[j] = max(res[j], num[i] + res[j - num[i]]);\n        cout << res[180] << endl;\n    }\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u63cf\u8ff0 hwf \u662f\u4e00\u4e2a\u975e\u5e38\u559c\u6b22\u5403\u62ab\u8428\u7684\u4eba\u3002\u67d0\u5929\uff0c\u5929\u4e0a\u6389\u4e0b\u4e86\u4e00\u5f20\u62ab\u8428\uff0c\u88ab hwf \u548c\u9ad8\u8001\u5e08\u770b\u5230\u4e86\u3002 \u9ad8\u8001\u5e08\u628a\u62ab\u8428\u5206 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[7,40],"class_list":["post-333","post","type-post","status-publish","format-standard","hentry","category-algo","tag-bjtuoj","tag-40"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/333","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=333"}],"version-history":[{"count":0,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/333\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=333"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=333"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}