{"id":115,"date":"2010-08-25T08:29:15","date_gmt":"2010-08-25T00:29:15","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=115"},"modified":"2012-03-03T08:29:31","modified_gmt":"2012-03-03T00:29:31","slug":"zoj-2604-little-brackets","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/zoj-2604-little-brackets\/","title":{"rendered":"ZOJ 2604. Little Brackets"},"content":{"rendered":"<h3>Brief description :<\/h3>\n<p>\u8ba1\u6570\uff0c\u6709 n \u4e2a\u8282\u70b9\u6df1\u5ea6\u4e3a k \u7684\u6709\u6839\u6811\u7684\u6570\u76ee\u3002<br \/>\n<!--more--><\/p>\n<h3>Analyse :<\/h3>\n<p>\u539f\u9898\u7684\u63cf\u8ff0\u662f\u62ec\u53f7\u5e8f\u5217\uff0c\u4e0d\u8fc7\u6211\u4eec\u77e5\u9053\u62ec\u53f7\u5e8f\u5217\u548c\u6811\u7ed3\u6784\u8ba1\u6570\u662f\u7b49\u4ef7\u7684\u3002\u3002<br \/>\n\u76ee\u524d\u8fd8\u4e0d\u77e5\u9053\u8fd9\u4e2a\u662f\u5426\u540c Catalan \u5e8f\u5217\u6709\u5173\uff0c\u5148\u6734\u7d20DP\u4e00\u4efd\u3002<\/p>\n<pre lang=\"cpp\" file=\"ZOJ_2604.cpp\">\r\n#include <iostream>\r\n#include \"bignum.h\"\r\nusing namespace std;\r\nconst int N = 50;\r\nconst int K = 50;\r\nbignum dp[K+1][N+1][N+1];\r\n\/\/ dp[i][l][r] \u8868\u793a\uff0c\u5f53\u524d\u6700\u5927\u6df1\u5ea6\u4e3a i \uff0c\u4e14\u6709l\u4e2a\u5de6\u62ec\u53f7\u548cr\u4e2a\u53f3\u62ec\u53f7\u7ec4\u6210\u7684\u62ec\u53f7\u5e8f\u5217\u7684\u6570\u76ee\u3002\r\nint n, k;\r\n\r\n\r\nvoid init(){\r\n    dp[0][0][0] = 1;\r\n\r\n    for (int i=1;i<=K;i++)\r\n        for (int l=1;l<=N;l++)\r\n            for (int r=max(l-i,0);r<=l;r++){\r\n                dp[i][l][r] = dp[i][l-1][r] + dp[i][l][r-1];\r\n                if (l - r == i)\r\n                    dp[i][l][r] += dp[i-1][l-1][r];\r\n            }\r\n}\r\n\r\nint main(){\r\n    init(); int T = 0; bool first_blood = true;\r\n    while (scanf(\"%d%d\", &#038;n, &#038;k) == 2 &#038;&#038; n != 0){\r\n        if (!first_blood) cout << endl; else first_blood = false;\r\n        cout << \"Case \" << ++T << \": \" << dp[k][n][n] << endl;\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Brief description : \u8ba1\u6570\uff0c\u6709 n \u4e2a\u8282\u70b9\u6df1\u5ea6\u4e3a k \u7684\u6709\u6839\u6811\u7684\u6570\u76ee\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-115","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-1R","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/115","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=115"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/115\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=115"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=115"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=115"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}