… \u95ee\u968f\u673a\u6570\u5217 {Ai} \u7684\u6700\u5927\u7edd\u5bf9\u5b50\u6bb5\u5408\u3002\u3002 (\u65e2\u6700\u5927\u5b50\u6bb5\u548c\u6216\u6700\u5c0f\u5b50\u6bb5\u548c\u7684\u7edd\u5bf9\u503c\u4e2d\u53d6\u8f83\u5927\u3002\u3002) .. .
\n(\u3002\u3002Ai \u53d6\u81ea {-1, 1}\u3002\u3002\u3002)<\/p>\n
<\/p>\n
… \u5206\u6790\u4e0d\u80fd\u7684\u6211\u3002\u3002\u3002\u53ea\u6709\u6253\u8868\u627e\u89c4\u5f8b\u4e86\u3002\u3002<\/p>\n
\r\nconst int N = 100;\r\nDB F[N], D[N], G[N], avg;\r\nint A[N], nn, n, m;\r\n\r\nint f(){\r\n int res = 0, sum = 0;\r\n\r\n REP(i, n){\r\n sum = max(0, sum + A[i]);\r\n checkMax(res, sum);\r\n }\r\n\r\n return res;\r\n}\r\n\r\nint g(){\r\n int res = 0, sum = 0;\r\n\r\n REP(i, n){\r\n sum = max(0, sum - A[i]);\r\n checkMax(res, sum);\r\n }\r\n\r\n return res;\r\n}\r\n\r\nvoid dfs(int k = 0){\r\n if (k == n){\r\n avg += max(f(), g());\r\n }\r\n else {\r\n FOR_1_N(A[k], -m, m){\r\n if (A[k])\r\n dfs(k+1);\r\n }\r\n }\r\n}\r\n\r\nint main(){\r\n\r\n \/\/freopen("in.txt", "r", stdin);\r\n\r\n m = 1, nn = 12; FOR_N(n, 1, nn){\r\n avg = 0, dfs(); \/\/avg \/= pow(2.0 * m, n);\r\n F[n] = avg;\r\n }\r\n\r\n REP(i, nn) D[i] = F[i+1] - F[i];\r\n REP(i, (nn-1)\/2) G[i] = D[2*(i+1)] \/ D[2*i];\r\n\r\n printf("F: ");\r\n REP(i, nn){\r\n printf("%.3lf ", F[i]);\r\n }\r\n puts("");\r\n\r\n printf("D: ");\r\n REP(i, nn-1){\r\n printf("%.3lf ", D[i]);\r\n }\r\n puts("");\r\n\r\n printf("G: ");\r\n REP(i, (nn-1)\/2){\r\n printf("%.3lf ", G[i]);\r\n }\r\n}\r\n<\/pre>\n\r\nconst int N = 1509;\r\nDB F[N], D[N], G[N];\r\nint nn, n, m;\r\n\r\nint main(){\r\n\r\n \/\/freopen("in.txt", "r", stdin);\r\n\r\n m = 1, nn = 1501;\r\n\r\n REP(i, (nn-1)\/2){\r\n G[i] = DB (2*i+1) \/ (2*(i+1));\r\n }\r\n\r\n D[0] = 1;\r\n REP(i, nn-1){\r\n D[i+1] = D[i] * G[i\/2];\r\n ++i, D[i+1] = D[i];\r\n }\r\n\r\n F[0] = 0;\r\n REP(i, nn-1){\r\n F[i+1] = F[i] + D[i];\r\n }\r\n\r\n REP_C(Case, RD()){\r\n printf("Case %d: %.6lf\\n", Case, F[RD()]);\r\n }\r\n}\r\n<\/pre>\nFurther discussion: <\/h3>\n
\u3002\u3002\u968f\u673a\u77e9\u9635\u7684\u6700\u5927\u5b50\u77e9\u9635\u3002\u3002
\n(\u8fd9\u4e2a\u65b9\u5411\u7684\u63a8\u5e7f\u592a\u590d\u6742\u4e86\u3002\u3002\u5148 hold \u3002\u3002\u3002)
\n\u3002\u3002\u3002\u968f\u673a\u5e8f\u5217\u7684\u6700\u5927\u5b50\u6bb5\u548c\u3002\u3002\u3002
\n(\u9898\u76ee\u4e2d\u53ef\u4ee5\u53d6\u7edd\u5bf9\u503c\u7684\u9650\u5236\u592a\u4e0d\u81ea\u7136\u4e86\u3002\u3002\u3002\u4f46\u662f\u53bb\u6389\u4ee5\u540e\u5b8c\u5168\u627e\u4e0d\u51fa\u89c4\u5f8b\u3002\u3002
\n\u5bf9\u6570\u7ec4\u7684\u53d6\u503c\u8303\u56f4\u8fdb\u884c\u63a8\u5e7f, {-m <= x <= m, x != 0, x \u662f\u6574\u6570}\u3002\u3002\u3002\n(\u540e\u4e24\u4e2a\u9650\u5236\u53bb\u6389\u540e\u4e5f\u53d8\u6210\u4e86\u5b8c\u5168\u4e0d\u540c\u7684\u95ee\u9898\u3002\u3002)\n\n\u4e24\u4e2a\u5f31\u5316\u3002\u3002\n\u3002\u3002\u53ea\u8003\u8651\u524d\u7f00\u548c (partial sums)\u3002\u3002\u3002\n\u3002\u3002\u53ea\u8003\u8651\u5355\u4e2a\u9879\u76ee\u7684\u6700\u5927\u503c\u3002\u3002\u3002\n\n\n\n\n\n
External link: <\/h3>\n
http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=4066<\/a>
\nhttp:\/\/math.stackexchange.com\/questions\/139159\/the-length-of-maximum-subsequence-in-a-random-sequence<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"Brief description: … \u95ee\u968f\u673a\u6570\u5217 {Ai} \u7684\u6700\u5927\u7edd\u5bf9\u5b50\u6bb5\u5408\u3002\u3002 (\u65e2\u6700\u5927\u5b50\u6bb5\u548c\u6216\u6700\u5c0f\u5b50\u6bb5\u548c\u7684\u7edd\u5bf9\u503c\u4e2d\u53d6\u8f83\u5927\u3002\u3002) .. . (\u3002\u3002Ai \u53d6\u81ea {-1, 1}\u3002\u3002\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":[47],"tags":[71],"class_list":["post-242","post","type-post","status-publish","format-standard","hentry","category-hdu","tag-71"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-3U","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/242","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=242"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/242\/revisions"}],"predecessor-version":[{"id":243,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/242\/revisions\/243"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=242"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=242"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=242"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}