{"id":746,"date":"2013-06-22T03:40:23","date_gmt":"2013-06-21T19:40:23","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=746"},"modified":"2013-06-22T07:18:08","modified_gmt":"2013-06-21T23:18:08","slug":"uva-6175-maximum-random-walk","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/uva-6175-maximum-random-walk\/","title":{"rendered":"UVa 6175. Maximum Random Walk"},"content":{"rendered":"<h3>Brief description: <\/h3>\n<p>\u3002\u3002\u4e00\u7ef4\u968f\u673a\u6e38\u52a8\u7cfb\u5217\u95ee\u9898\uff0c\u5411\u53f3\u7684\u6982\u7387\u4e3a r\uff0c\u5411\u5de6\u7684\u6982\u7387\u4e3a l\uff0c\u9759\u6b62\u7684\u6982\u7387\u4e3a s\u3002<br \/>\n\u8be2\u95ee n \u6b65\u540e rightmost (\u5386\u53f2\u4e0a\u7684\u6700\u53f3\u4f4d\u7f6e) \u7684\u671f\u671b\u3002<\/p>\n<p><!--more--><\/p>\n<h3>Analysis: <\/h3>\n<p><a href=\"https:\/\/www.shuizilong.com\/house\/archives\/north-america-greater-ny-2012\/\">&#8230; \u63a5\u4e0a\u6587\u3002\u3002\uff09<\/a><br \/>\n\u6211\u770b\u5230\u63d0\u4ea4\u8bb0\u5f55\u91cc\u6709\u4e2a 93ms \u7684\u7a0b\u5e8f\u3002\u3002\u3002\u53ef\u89c1\u4f4e\u4e8e O(n3) \u7684\u505a\u6cd5\u662f\u5b58\u5728\u7684\u3002\u3002\u3002<\/p>\n<p><img decoding=\"async\" src=\"http:\/\/upload.wikimedia.org\/wikipedia\/commons\/f\/f4\/Catalan_number_4x4_grid_example.svg\" alt=\"\" \/><\/p>\n<p>\u9996\u5148\u8981\u7528\u5230\u5e7f\u4e49 <a href=\"http:\/\/en.wikipedia.org\/wiki\/Catalan_number\">Catalan \u6570<\/a>\u3002\u3002<br \/>\n\u3002Catalan(n, m, k): \u5bbd n\u3001 \u957f m \u4e0d\u8d8a\u8fc7\u5bf9\u89d2\u7ebf\u7684\u65b9\u6848\u6570\u3002\u3002\u5bf9\u89d2\u7ebf\u5411\u4e0a\u5e73\u79fb k \u683c\u3002\u3002\u3002\u3002\u3002\u3002\u7ed3\u679c\u662f <\/p>\n<p>$$!\\binom{n+m}{n} &#8211; \\binom{n+m}{n+k+1}$$\u3002<\/p>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Catalan_number#Third_proof\">\u8bc1\u660e\u53c2\u8003\u955c\u50cf\u6cd5\u3002\u3002\u3002<\/a><br \/>\n\u3002\u3002(\u53e6\u5bf9 k = 0 \u7684\u60c5\u51b5&#8230;\u53c2\u89c1\u3002\u3002<a href=\"http:\/\/www.rqnoj.cn\/Problem_293.html\">RQ 293. \u7f51\u683c<\/a><\/p>\n<p>\u4e0b\u9762\u8003\u8651\u4f18\u5316 O(n3) \u7684\u590d\u6742\u5ea6\u3002\u3002\u65b9\u6cd5\u662f\u679a\u4e3e rightmost\u3002<br \/>\n\u3002\u3002\u7136\u540e\u6211\u4eec\u8bbe\u6cd5\u8ba1\u7b97\u51fa\u5bf9\u5e94\u7684\u6982\u7387\u3002\u3002<br \/>\n\u7531\u4e8e\u968f\u673a\u79fb\u52a8\u8fc7\u7a0b\u5bf9\u5e94\u8fc7\u53bb\u7684\u65f6\u5019\u3002\u3002\u5e76\u4e0d\u4fdd\u8bc1\u4e00\u5b9a\u505c\u7559\u5728\u67d0\u4e2a (n, m) \u3002\u3002\u6240\u4ee5\u6211\u4eec\u8fd8\u6709\u518d\u679a\u4e3e\u6c42\u548c\u4e00\u6b21\u3002\u3002\u3002<br \/>\n\u3002\u3002\u3002\u3002\u8fd9\u6837\u89e3\u51b3\u4e86 l = r = 0.5 \u7684\u60c5\u51b5\u3002\u3002<\/p>\n<p>\u3002\u3002\u5728\u8003\u8651\u65f6\u6ede\u4e4b\u540e\u6211\u7684\u7ed3\u679c\u5c31\u4e0d\u5bf9\u4e86\u3002\u3002\u4f46\u662f\u4e5f\u53ef\u80fd\u662f\u4e4b\u524d\u5c31\u9519\u4e86\u3002\u3002(\u800c\u4e14\u76ee\u524d\u662f\u679a\u4e3e\u65f6\u6ede\u3002\u3002\u603b\u8ba1\u590d\u6742\u5ea6\u5df2\u7ecf\u662f O(n3) \u4e86\u3002\u3002\u3002\u3002<br \/>\n\u3002\u3002\u4e0b\u9762\u7684\u4ee3\u7801\u6709 bug\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; collapse: false; first-line: 1; light: false; title: example-filename.cpp; toolbar: true; notranslate\" title=\"example-filename.cpp\">\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 1009;\r\nDB C&#x5B;N]&#x5B;N], l, r, s;\r\nint n;\r\n\r\nDB Catalan(int n, int m, int k){ \/\/ \u5e7f\u4e49\u5361\u5854\u5170\u5e8f\u5217\r\n    assert(m-n&lt;=k);\r\n    return C&#x5B;n+m]&#x5B;n] - (n+k+1 &lt;= n+m ? C&#x5B;n+m]&#x5B;n+k+1] : 0);\r\n}\r\n\r\nDB Probfact(int a, int b){\r\n    return pow(l, a) * pow(r, b);\r\n}\r\n\r\nDB g(int k){ \/\/ rightmost &lt;= k \u7684\u6982\u7387\r\n    DB res = 0;\r\n\r\n    REP(i, n+1){\r\n        if (2*i-n&gt;k) break;\r\n        res += Catalan(n-i, i, k) * Probfact(n-i, i);\r\n    }\r\n\r\n    return res;\r\n}\r\n\r\nDB p(int k){ \/\/ rightmost \u4e3a k \u7684\u6982\u7387\r\n    return g(k) - g(k-1);\r\n}\r\n\r\nDB f(int n){\r\n    DB res = 0; REP_1(i, n){\r\n        \/\/cout &lt;&lt; i &lt;&lt; &quot;:&quot; &lt;&lt; p(i) &lt;&lt; endl;\r\n        res += i * p(i);\r\n    }\r\n    return res;\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    REP(i, N){C&#x5B;i]&#x5B;0] = 1; REP_1(j, i) C&#x5B;i]&#x5B;j] = C&#x5B;i-1]&#x5B;j-1] + C&#x5B;i-1]&#x5B;j];}\r\n\r\n    Rush{\r\n        scanf(&quot;%*d%d&quot;, &amp;n);\r\n        RF(l, r); s = 1 - l - r; l \/= 1-s, r \/= 1-s;\r\n        DB res = 0; REP(i, n+1) res += f(n-i) * C&#x5B;n]&#x5B;i] * pow(s, i) * pow(1-s, n-i); \/\/ \u679a\u4e3e\u65f6\u6ede\u3002\r\n        OT(res);\r\n    }\r\n}\r\n<\/pre>\n<p><a href=\"http:\/\/acm.hust.edu.cn\/vjudge\/problem\/viewSource.action?id=1231769\">\u5b8c\u6574 bug \u4ee3\u7801\u3002\u3002<\/a><\/p>\n<h3>External link: <\/h3>\n<p>.. .<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Brief description: \u3002\u3002\u4e00\u7ef4\u968f\u673a\u6e38\u52a8\u7cfb\u5217\u95ee\u9898\uff0c\u5411\u53f3\u7684\u6982\u7387\u4e3a r\uff0c\u5411\u5de6\u7684\u6982\u7387\u4e3a l\uff0c\u9759\u6b62\u7684\u6982\u7387\u4e3a s\u3002 \u8be2\u95ee n \u6b65\u540e rightmost (\u5386\u53f2\u4e0a\u7684\u6700\u53f3\u4f4d\u7f6e) \u7684\u671f\u671b\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":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[31],"tags":[],"class_list":["post-746","post","type-post","status-publish","format-standard","hentry","category-uva"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-c2","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/746","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=746"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/746\/revisions"}],"predecessor-version":[{"id":747,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/746\/revisions\/747"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=746"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=746"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=746"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}