wqs \u4e8c\u5206\u663e\u7136\uff0c\u6700\u591a\u6bcf\u8f6e\u5f97\u5206\u662f 1\uff0clambda \u4e0a\u9650\u53ef\u7f6e\u4e3a 1\u3002
\n\u76f4\u63a5 dp \u590d\u6742\u5ea6 O(n2) \u53ef\u4ee5\u62ff 34 \u5206\u3002<\/p>\n
\nconst int N = int(1e5) + 9;\npair<DB, int> f[N];\nint q[N], cz, op;\nint n, k;\n\nbool ok(DB lambda) {\n cz = 0, op = 0; q[cz] = 0; REP_1(i, n) {\n auto g = [&](int j){\n return MP(f[j].fi + (DB)(i-j)\/i - lambda, f[j].se + 1);\n };\n f[i] = {0, 0};\n REP(j, i) checkMax(f[i], g(j));\n }\n return f[n].se <= k;\n}\n\nDB gao() {\n DB l = 0, r = 1;\n DO(133) {\n DB m = (l + r) \/ 2;\n ok(m) ? r = m : l = m;\n }\n ok(l);\n return f[n].fi + l*k;\n}\n\nint main() {\n\n#ifndef ONLINE_JUDGE\n freopen("in.txt", "r", stdin);\n \/\/freopen("out.txt", "w", stdout);\n#endif\n RD(n, k);\n printf("%.9f\\n", gao());\n}\n\n<\/pre>\n\u8fdb\u4e00\u6b65\u89c2\u5bdf\uff0c\u663e\u7136\u53ef\u4ee5\u659c\u7387 dp\uff0c\u590d\u6742\u5ea6 O(n)\u3002<\/p>\n
\nconst int N = int(1e5) + 9;\npair<DB, int> f[N];\nint q[N], cz, op;\nint n, k;\n\n\/\/ f[j].fi - j\/i\n\/\/ b = y - kx\n\/\/ f[i] , f[j], 1\/i, j\n\nDB det(DB x1, DB y1, DB x2, DB y2){\n return x1<em>y2 - x2<\/em>y1;\n}\n\nint dett(int a, int b, int c) {\n DB t = det(b-a, f[b].fi-f[a].fi, c-a, f[c].fi-f[a].fi);\n return t < 0 ? -1 : t > 0;\n}\n\nbool ok(DB lambda) {\n cz = 0, op = 0; q[cz] = 0; REP_1(i, n) {\n auto g = [&](int j){\n return MP(f[j].fi + (DB)(i-j)\/i - lambda, f[j].se + 1);\n };\n while (cz < op && g(q[cz]) <= g(q[cz+1])) ++cz;\n f[i] = g(q[cz]);\n while (cz < op && dett(q[op-1], q[op], i) > 0) --op;\n q[++op] = i;\n }\n return f[n].se <= k;\n}\n\nDB gao() {\n DB l = 0, r = 1;\n DO(133) {\n DB m = (l + r) \/ 2;\n ok(m) ? r = m : l = m;\n }\n\n<pre><code>ok(l);\nreturn f[n].fi + l*k;\n<\/code><\/pre>\n\n}\n\nint main() {\n\n#ifndef ONLINE_JUDGE\n freopen("in.txt", "r", stdin);\n \/\/freopen("out.txt", "w", stdout);\n#endif\n RD(n, k);\n printf("%.9f\\n", gao());\n}\n<\/pre>\n\u4f3c\u4e4e\u4e5f\u53ef\u4ee5\u76f4\u63a5\u4e8c\u5206\u5bfc\u6570\uff1f<\/p>\n","protected":false},"excerpt":{"rendered":"
wqs \u4e8c\u5206\u663e\u7136\uff0c\u6700\u591a\u6bcf\u8f6e\u5f97\u5206\u662f 1\uff0clambda \u4e0a\u9650\u53ef\u7f6e\u4e3a 1\u3002 \u76f4\u63a5 dp \u590d\u6742\u5ea6 O(n2) \u53ef\u4ee5\u62ff 34 \u5206\u3002 const int N = int(1e5) + 9; pair<DB, int> f[N]; int q[N], cz, op; int n, k; bool ok(DB lambda) { cz = 0, op = 0; q[cz] = 0; REP_1(i, n) { auto g = [&](int j){ return MP(f[j].fi + (DB)(i-j)\/i – […]<\/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":[1],"tags":[],"class_list":["post-3314","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-Rs","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3314","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=3314"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3314\/revisions"}],"predecessor-version":[{"id":3315,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3314\/revisions\/3315"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=3314"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=3314"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=3314"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}