{"id":802,"date":"2019-03-10T13:52:11","date_gmt":"2019-03-10T05:52:11","guid":{"rendered":"http:\/\/www.guanhaobo.cn\/?p=8"},"modified":"2019-03-10T13:52:11","modified_gmt":"2019-03-10T05:52:11","slug":"poj-1664-%e6%94%be%e8%8b%b9%e6%9e%9c","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=802","title":{"rendered":"POJ 1664 — \u653e\u82f9\u679c"},"content":{"rendered":"

\u9898\u76ee\u5927\u610f<\/h4>\n

\u628aM\u4e2a\u540c\u6837\u7684\u82f9\u679c\u653e\u5728N\u4e2a\u540c\u6837\u7684\u76d8\u5b50\u91cc\uff0c\u5141\u8bb8\u6709\u7684\u76d8\u5b50\u7a7a\u7740\u4e0d\u653e\uff0c\u95ee\u5171\u6709\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u5206\u6cd5\uff1f\uff08\u7528K\u8868\u793a\uff095\uff0c1\uff0c1\u548c1\uff0c5\uff0c1 \u662f\u540c\u4e00\u79cd\u5206\u6cd5\u3002<\/p>\n

<\/p>\n

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

http:\/\/poj.org\/problem?id=1664<\/a><\/p>\n

\u8f93\u5165<\/h4>\n

\u7b2c\u4e00\u884c\u662f\u6d4b\u8bd5\u6570\u636e\u7684\u6570\u76eet\uff080 <= t <= 20\uff09\u3002\u4ee5\u4e0b\u6bcf\u884c\u5747\u5305\u542b\u4e8c\u4e2a\u6574\u6570M\u548cN\uff0c\u4ee5\u7a7a\u683c\u5206\u5f00\u30021<=M\uff0cN<=10\u3002<\/p>\n

\u8f93\u51fa<\/h4>\n

\u5bf9\u8f93\u5165\u7684\u6bcf\u7ec4\u6570\u636eM\u548cN\uff0c\u7528\u4e00\u884c\u8f93\u51fa\u76f8\u5e94\u7684K\u3002<\/p>\n

\u6837\u4f8b\u8f93\u5165<\/h4>\n
1\n7 3\n<\/code><\/pre>\n
\u6837\u4f8b\u8f93\u51fa<\/h4>\n
8\n<\/code><\/pre>\n
\u95ee\u9898\u5206\u6790<\/h4>\n
\u5047\u8bbei\u4e2a\u82f9\u679c\ud83c\udf4e\u653e\u8fdbk\u4e2a\u76d8\u5b50\u7684\u5206\u6cd5\u4e2a\u6570\u4e3a f(i,k)\u3002<\/p>\n
i<k \u65f6\uff0c\u81f3\u5c11\u6709k-i\u4e2a\u76d8\u5b50\u4e3a\u7a7a\uff0c\u95ee\u9898\u8f6c\u5316\u4e3ai\u4e2a\u82f9\u679c\u653e\u8fdbi\u4e2a\u76d8\u5b50\uff0c\u56e0\u6b64 f(i,k) = f(i,i) \uff1b<\/p>\n
i==k \u65f6\uff0c\u5206\u4e3a\u6709\u7a7a\u76d8\u5b50\u548c\u65e0\u7a7a\u76d8\u5b50\u4e24\u79cd\u60c5\u51b5\uff0c\u6709\u7a7a\u76d8\u5b50\u76f8\u5f53\u4e8e\u81f3\u5c11\u6709\u4e00\u4e2a\u7a7a\u76d8\u5b50\uff0c\u4e3a f(i,k-1)\uff1b\u65e0\u7a7a\u76d8\u5b50\u53ea\u80fd\u4e00\u4e2a\u76d8\u5b50\u653e\u4e00\u4e2a\u82f9\u679c\uff0c\u4e3a1\uff1b\u56e0\u6b64 f(i,k) = f(i,k-1) + 1\uff1b<\/p>\n
i>k\u65f6\uff0c\u5206\u4e3a\u6709\u7a7a\u76d8\u5b50\u548c\u65e0\u7a7a\u76d8\u5b50\u4e24\u79cd\u60c5\u51b5\uff0c\u6709\u7a7a\u76d8\u5b50\u76f8\u5f53\u4e8e\u81f3\u5c11\u6709\u4e00\u4e2a\u7a7a\u76d8\u5b50\uff0c\u4e3a f(i,k-1)\uff1b\u65e0\u7a7a\u76d8\u5b50\u5219\u6bcf\u4e2a\u76d8\u5b50\u81f3\u5c11\u653e\u4e00\u4e2a\u82f9\u679c\uff0c\u76f8\u5f53\u4e8e\u6254\u6389k\u4e2a\u82f9\u679c\uff0c\u4e3a f(i-k,k)\uff1b\u56e0\u6b64 f(i,k) = f(i,k-1) + f(i-k,k)\uff1b<\/p>\n
\u9012\u5f52\u7684\u51fa\u53e3\u662f i ==1 \u6216 k ==1.<\/p>\n
AC\u4ee3\u7801<\/h4>\n
#include <iostream>\nusing namespace std;\n\nint f(int i, int k); \/\/i\u4e2a\u82f9\u679c\u653e\u5165k\u4e2a\u76d8\u5b50\n\nint main()\n{\n    int t, m, n;\n    cin >> t;\n    while (t--)\n    {\n        cin >> m >> n;\n        cout << f(m, n) << endl;\n    }\n    return 0;\n}\n\nint f(int i, int k)\n{\n    if (i == 1 || k == 1)\n        return 1;\n    if (i < k)\n        return f(i, i);\n    if (i == k)\n        return f(i, k - 1) + 1; \/\/\u6709\u7a7a\u76d8\u5b50\uff0c\u65e0\u7a7a\u76d8\u5b50\n    if (i > k)\n        return f(i, k - 1) + f(i - k, k); \/\/\u6709\u7a7a\u76d8\u5b50\uff0c\u65e0\u7a7a\u76d8\u5b50\n}\n<\/code><\/pre>\n
\u6ce8\u610f\u4e8b\u9879<\/h4>\n
\u8fd9\u9053\u9898\u4e5f\u53ef\u4ee5\u6539\u5199\u6210\u9012\u63a8\uff0c\u5c06\u9898\u76ee\u8303\u56f4\u5185\u7684\u6240\u6709\u7b54\u6848\u90fd\u8ba1\u7b97\u51fa\u6765\uff0c\u5b58\u5165\u6570\u7ec4\u4e2d\uff0c\u66f4\u8282\u7701\u65f6\u95f4\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u5927\u610f \u628aM\u4e2a\u540c\u6837\u7684\u82f9\u679c\u653e\u5728N\u4e2a\u540c\u6837\u7684\u76d8\u5b50\u91cc\uff0c\u5141\u8bb8\u6709\u7684\u76d8\u5b50\u7a7a\u7740\u4e0d\u653e\uff0c\u95ee\u5171\u6709\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u5206\u6cd5\uff1f\uff08\u7528K\u8868\u793a\uff095\uff0c […]<\/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":[25,64],"class_list":["post-802","post","type-post","status-publish","format-standard","hentry","category-algo","tag-poj","tag-64"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/802","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=802"}],"version-history":[{"count":0,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/802\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=802"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=802"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=802"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}