{"id":344,"date":"2019-10-06T22:34:49","date_gmt":"2019-10-06T14:34:49","guid":{"rendered":"http:\/\/www.guanhaobo.cn\/?p=344"},"modified":"2019-10-06T22:34:49","modified_gmt":"2019-10-06T14:34:49","slug":"%e7%99%be%e7%bb%83-2759-%e7%a5%9e%e5%a5%87%e7%9a%84%e5%8f%a3%e8%a2%8b2","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=344","title":{"rendered":"\u767e\u7ec3 2759 \u2014 \u795e\u5947\u7684\u53e3\u888b(2)"},"content":{"rendered":"

\u63cf\u8ff0<\/h3>\n

\u6709\u4e00\u4e2a\u795e\u5947\u7684\u53e3\u888b\uff0c\u603b\u7684\u5bb9\u79ef\u662f400\uff0c\u7528\u8fd9\u4e2a\u53e3\u888b\u53ef\u4ee5\u53d8\u51fa\u4e00\u4e9b\u7269\u54c1\uff0c\u8fd9\u4e9b\u7269\u54c1\u7684\u603b\u4f53\u79ef\u5fc5\u987b\u662f400\u3002John\u73b0\u5728\u6709n\u4e2a\u60f3\u8981\u5f97\u5230\u7684\u7269\u54c1\uff0c\u6bcf\u4e2a\u7269\u54c1\u7684\u4f53\u79ef\u5206\u522b\u662fa1\uff0ca2\u2026\u2026an\u3002John\u53ef\u4ee5\u4ece\u8fd9\u4e9b\u7269\u54c1\u4e2d\u9009\u62e9\u4e00\u4e9b\uff0c\u5982\u679c\u9009\u51fa\u7684\u7269\u4f53\u7684\u603b\u4f53\u79ef\u662f400\uff0c\u90a3\u4e48\u5229\u7528\u8fd9\u4e2a\u795e\u5947\u7684\u53e3\u888b\uff0cJohn\u5c31\u53ef\u4ee5\u5f97\u5230\u8fd9\u4e9b\u7269\u54c1\u3002\u73b0\u5728\u7684\u95ee\u9898\u662f\uff0cJohn\u6709\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u9009\u62e9\u7269\u54c1\u7684\u65b9\u5f0f\u3002<\/p>\n

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

http:\/\/bailian.openjudge.cn\/practice\/2759<\/a><\/p>\n

\u8f93\u5165<\/h3>\n

\u8f93\u5165\u7684\u7b2c\u4e00\u884c\u662f\u6b63\u6574\u6570n (1 <= n <= 200)\uff0c\u8868\u793a\u4e0d\u540c\u7684\u7269\u54c1\u7684\u6570\u76ee\u3002\u63a5\u4e0b\u6765\u7684n\u884c\uff0c\u6bcf\u884c\u6709\u4e00\u4e2a1\u5230400\u4e4b\u95f4\u7684\u6b63\u6574\u6570\uff0c\u5206\u522b\u7ed9\u51faa1\uff0ca2\u2026\u2026an\u7684\u503c\u3002<\/p>\n

\u8f93\u51fa<\/h3>\n

\u8f93\u51fa\u4e0d\u540c\u7684\u9009\u62e9\u7269\u54c1\u7684\u65b9\u5f0f\u7684\u6570\u76ee\u5bf910000\u53d6\u6a21\u7684\u7ed3\u679c\uff08\u56e0\u4e3a\u7ed3\u679c\u53ef\u80fd\u5f88\u5927\uff0c\u4e3a\u4e86\u907f\u514d\u9ad8\u7cbe\u5ea6\u8ba1\u7b97\uff0c\u53ea\u8981\u6c42\u5bf910000\u53d6\u6a21\u7684\u7ed3\u679c\uff09\u3002<\/p>\n

\u6837\u4f8b\u8f93\u5165<\/h3>\n
3\n200\n200\n200\n<\/code><\/pre>\n
\u6837\u4f8b\u8f93\u51fa<\/h3>\n
3<\/code><\/p>\n
\u9898\u76ee\u5206\u6790<\/h3>\n
\u8fd9\u9053\u9898\u548c\u767e\u7ec3 2755 \u2014 \u795e\u5947\u7684\u53e3\u888b<\/a>\u662f\u76f8\u540c\u7684\uff0c\u53ea\u662f\u6570\u636e\u8303\u56f4\u4e0d\u540c\uff0c\u53e6\u5916\u672c\u9898\u591a\u4e86\u5bf9 10000 \u53d6\u6a21\u3002
\n\u672c\u9898\u4e2d n \u6700\u5927\u4e3a 200\uff0c\u4f7f\u7528\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u4f1a\u8d85\u65f6\u3002<\/p>\n
\u52a8\u6001\u89c4\u5212\uff08\u9012\u5f52\uff09<\/h5>\n
\u8bbe\u7b2ci\u4e2a\u7269\u54c1\u7684\u4f53\u79ef\u4e3av[i]\uff08\u4e3a\u5565\u4e0d\u7528a[i]\u5462\uff1f\u56e0\u4e3a\u6211\u4ee3\u7801\u91cc\u5199\u7684\u662fv\uff0c\u61d2\u5f97\u6539\u4e86\uff09
\n\u8bbef(i, j)<\/code>\u8868\u793a\u5728\u524di\u4e2a\u7269\u54c1\u4e2d\u6311\u9009\u7269\u54c1\uff0c\u603b\u4f53\u79ef\u4e3aj\u7684\u9009\u62e9\u65b9\u5f0f\u7684\u6570\u76ee\u3002
\n\u90a3\u4e48\uff0cf(n, 400)<\/code>\u5c31\u662f\u7b54\u6848\u3002
\n\u5982\u679cv[i] <= j<\/code>\uff0c\u90a3\u4e48\u5bf9\u4e8e\u7b2ci\u4e2a\u7269\u54c1\uff0c\u53ef\u4ee5\u9009\u62e9\u653e\u5165\u53e3\u888b\u6216\u4e0d\u653e\u5165\u53e3\u888b\u3002\u5982\u679c\u628a\u5b83\u653e\u5165\u53e3\u888b\uff0c\u90a3\u4e48\u9009\u62e9\u65b9\u5f0f\u6709f(i, j-v[i])<\/code>\u79cd\uff1b\u5982\u679c\u4e0d\u628a\u5b83\u653e\u5165\u53e3\u888b\uff0c\u90a3\u4e48\u9009\u62e9\u65b9\u5f0f\u6709f(i-1, j)<\/code>\u79cd\u3002
\n\u8fd9\u65f6\uff0cf(i, j) = f(i-1, j-v[i]) + f(i-1, j)<\/code>
\n\u5982\u679cv[i] > j<\/code>\uff0c\u90a3\u4e48\u5bf9\u4e8e\u7b2ci\u4e2a\u7269\u54c1\uff0c\u53ea\u80fd\u9009\u62e9\u4e0d\u653e\u5165\u53e3\u888b\u3002
\n\u8fd9\u65f6\uff0cf(i, j) = f(i-1, j)<\/code>
\n\u73b0\u5728\u5c31\u53ef\u4ee5\u4f7f\u7528\u9012\u5f52\u7684\u65b9\u6cd5\u5199\u51fa\u51fd\u6570 f(int i, int j)<\/code>\u4e86\u3002
\n\u4f46\u662f\uff0c\u5f88\u5bb9\u6613\u4f1a\u53d1\u73b0\uff0c\u8fd9\u91cc\u9762\u5b58\u5728\u5f88\u4e25\u91cd\u7684\u91cd\u590d\u8ba1\u7b97\u7684\u95ee\u9898\u3002
\n\u6240\u4ee5\uff0c\u6211\u4eec\u6dfb\u52a0\u4e00\u4e2a\u6570\u7ec4\uff0c\u8bbenum[i][j]<\/code>\u8868\u793af(i, j)<\/code>\u7684\u503c\uff0c\u5c06\u8ba1\u7b97\u51fa\u7684f(i, j)<\/code>\u4fdd\u5b58\u4e0b\u6765\u5373\u53ef\u3002\u4e0b\u6b21\u518d\u9700\u8981\u4f7f\u7528f(i, j)<\/code>\u7684\u65f6\u5019\uff0c\u76f4\u63a5\u4f7f\u7528num[i][j]<\/code>\u5373\u53ef\u3002
\n\u8fd9\u53eb\u505a\u8bb0\u5fc6\u5316\u641c\u7d22\u3002
\n\u5f53\u7136\u4e86\uff0c\u9012\u5f52\u51fd\u6570\u662f\u8981\u6709\u51fa\u53e3\u7684\uff0c\u5177\u4f53\u7684\u6211\u5c31\u4e0d\u5206\u6790\u4e86\uff0c\u5927\u5bb6\u53ef\u4ee5\u53c2\u8003\u6211\u7684\u4ee3\u7801\u3002<\/p>\n
\u52a8\u6001\u89c4\u5212\uff08\u9012\u63a8\uff09<\/h5>\n
\u548c\u4e0a\u9762\u7684\u63a8\u7406\u7c7b\u4f3c\u3002
\n\u8bbenum[i][j]<\/code>\u8868\u793a\u5728\u524di\u4e2a\u7269\u54c1\u4e2d\u6311\u9009\u7269\u54c1\uff0c\u603b\u4f53\u79ef\u4e3aj\u7684\u9009\u62e9\u65b9\u5f0f\u7684\u6570\u76ee\u3002
\n\u90a3\u4e48\uff0cnum[n][400]<\/code>\u5c31\u662f\u7b54\u6848\u3002
\n\u5982\u679cv[i] <= j<\/code>\uff0c\u90a3\u4e48\u5bf9\u4e8e\u7b2ci\u4e2a\u7269\u54c1\uff0c\u53ef\u4ee5\u9009\u62e9\u653e\u5165\u53e3\u888b\u6216\u4e0d\u653e\u5165\u53e3\u888b\u3002\u5982\u679c\u628a\u5b83\u653e\u5165\u53e3\u888b\uff0c\u90a3\u4e48\u9009\u62e9\u65b9\u5f0f\u6709num[i][j-v[i]]<\/code>\u79cd\uff1b\u5982\u679c\u4e0d\u628a\u5b83\u653e\u5165\u53e3\u888b\uff0c\u90a3\u4e48\u9009\u62e9\u65b9\u5f0f\u6709num[i-1][j]<\/code>\u79cd\u3002
\n\u8fd9\u65f6\uff0cnum[i][j] = num[i-1][j-v[i]] + num[i-1][j]<\/code>
\n\u5982\u679cv[i] > j<\/code>\uff0c\u90a3\u4e48\u5bf9\u4e8e\u7b2ci\u4e2a\u7269\u54c1\uff0c\u53ea\u80fd\u9009\u62e9\u4e0d\u653e\u5165\u53e3\u888b\u3002
\n\u8fd9\u65f6\uff0cnum[i][j] = num[i-1][j]<\/code><\/p>\n
if (v[i] <= j)\n    num[i][j] = (num[i - 1][j - v[i]] % 10000 + num[i - 1][j] % 10000) % 10000;\nelse\n    num[i][j] = num[i - 1][j] % 10000;\n<\/code><\/pre>\n
\u6211\u4eec\u53d1\u73b0\uff0cnum[i][j]<\/code>\u53ea\u548cnum[i-1][j-v[i]]<\/code>\u4ee5\u53canum[i-1][j]<\/code>\u6709\u5173\uff0c\u540e\u9762\u4e24\u4e2a\u5728\u4e0b\u6807\u4e0a\u90fd\u662f\u5c0f\u4e8enum[i][j]<\/code>\u7684\u3002
\n\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528\u4e24\u5c42\u5faa\u73af\uff0c\u4ecenum[1][1]<\/code>\u63a8\u5230num[n][400]<\/code>\u3002
\n\u5f53\u7136\uff0c\u9700\u8981\u5148\u5bf9num\u6570\u7ec4\u505a\u4e00\u4e9b\u521d\u59cb\u5316\u7684\u5de5\u4f5c\u3002\u5177\u4f53\u89c1\u4ee3\u7801\u3002<\/p>\n
\u52a8\u6001\u89c4\u5212\uff08\u9012\u63a8+\u4f18\u5316\uff09<\/h5>\n
\u5728\u4e0a\u9762\u7684\u57fa\u7840\u4e0a\uff0cnum[i, j]<\/code>\u5728\u7b2c\u4e00\u7ef4\u5ea6\u4e0a\u53ea\u548cnum[i-1]<\/code>\u6709\u5173\u3002
\n\u6240\u4ee5 num \u6570\u7ec4\u7684\u7b2c\u4e00\u4e2a\u7ef4\u5ea6\u5176\u5b9e\u53ef\u4ee5\u7701\u7565\u3002
\n\u53e6\u5916\uff0c\u5728v[i] > j<\/code>\u65f6\uff0cnum[i][j] = num[i - 1][j]<\/code>\uff0c\u5728\u7701\u7565\u4e86\u7b2c\u4e00\u7ef4\u5ea6\u540e\uff0c\u8fd9\u4e2a\u4e5f\u53ef\u4ee5\u4e0d\u5199\u4e86\u3002
\nnum[400]<\/code>\u5c31\u662f\u6700\u7ec8\u7b54\u6848\u3002<\/p>\n
AC\u4ee3\u7801<\/h3>\n
\u52a8\u6001\u89c4\u5212\uff08\u9012\u5f52\uff09<\/h5>\n
#include <iostream>\n#include <cstring>\nusing namespace std;\nint num[205][405], v[205];\n\nint f(int n, int sum)\n{\n    if (sum == 0) \/\/sum==0\u8981\u653e\u5728n==0\u524d\u9762\uff0c\u56e0\u4e3anum[0][0]\u7684\u503c\u5e94\u8be5\u4e3a1\n        return 1;\n    if (n == 0)\n        return 0;\n    if (num[n][sum] != -1)\n        return num[n][sum];\n    if (v[n] <= sum)\n        num[n][sum] = (f(n - 1, sum - v[n]) % 10000 + f(n - 1, sum) % 10000) % 10000;\n    else\n        num[n][sum] = f(n - 1, sum) % 10000;\n    return num[n][sum];\n}\n\nint main()\n{\n    int i, n;\n    memset(num, -1, sizeof((num)));\n    cin >> n;\n    for (i = 1; i <= n; i++)\n        cin >> v[i];\n    cout << f(n, 400) << endl;\n    return 0;\n}\n<\/code><\/pre>\n
\u52a8\u6001\u89c4\u5212\uff08\u9012\u63a8\uff09<\/h5>\n
#include <iostream>\nusing namespace std;\nint num[205][405] = {0}, v[205];\nint main()\n{\n    int i, j, n;\n    cin >> n;\n    for (i = 0; i < 205; i++)\n        num[i][0] = 1; \/\/\u8fd9\u4e00\u70b9\u975e\u5e38\u91cd\u8981\uff0c\u5bf9\u5e94\u4e0b\u4e00\u6761\u6ce8\u91ca\uff0c\u5f53j==v[i]\u65f6\uff0c\u7b97\u4e00\u79cd\n    for (i = 1; i <= n; i++)\n        cin >> v[i];\n    for (i = 1; i <= n; i++)\n    {\n        for (j = 1; j < 401; j++)\n        {\n            if (v[i] <= j)\n                num[i][j] = (num[i - 1][j - v[i]] % 10000 + num[i - 1][j] % 10000) % 10000; \/\/\u5bf9\u5e94\u4e0a\u4e00\u6761\u6ce8\u91ca\n            else\n                num[i][j] = num[i - 1][j] % 10000;\n        }\n    }\n    cout << num[n][400] << endl;\n    return 0;\n}\n<\/code><\/pre>\n
\u52a8\u6001\u89c4\u5212\uff08\u9012\u63a8+\u4f18\u5316\uff09<\/h5>\n
#include <iostream>\nusing namespace std;\nint num[405] = {1}, v[205];\nint main()\n{\n    int i, j, n;\n    cin >> n;\n    for (i = 1; i <= n; i++)\n        cin >> v[i];\n    for (i = 1; i <= n; i++)\n        for (j = 400; j >= v[i]; j--)\n            num[j] = (num[j - v[i]] % 10000 + num[j] % 10000) % 10000;\n    cout << num[400] << endl;\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u63cf\u8ff0 \u6709\u4e00\u4e2a\u795e\u5947\u7684\u53e3\u888b\uff0c\u603b\u7684\u5bb9\u79ef\u662f400\uff0c\u7528\u8fd9\u4e2a\u53e3\u888b\u53ef\u4ee5\u53d8\u51fa\u4e00\u4e9b\u7269\u54c1\uff0c\u8fd9\u4e9b\u7269\u54c1\u7684\u603b\u4f53\u79ef\u5fc5\u987b\u662f400\u3002John\u73b0 […]<\/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":[40,58,61,64],"class_list":["post-344","post","type-post","status-publish","format-standard","hentry","category-algo","tag-40","tag-58","tag-61","tag-64"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/344","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=344"}],"version-history":[{"count":0,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/344\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=344"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=344"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=344"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}