{"id":3023,"date":"2023-06-11T06:27:06","date_gmt":"2023-06-10T22:27:06","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=3023"},"modified":"2023-06-11T06:27:29","modified_gmt":"2023-06-10T22:27:29","slug":"luogu-p1973-noi2011-noi-%e5%98%89%e5%b9%b4%e5%8d%8e","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/luogu-p1973-noi2011-noi-%e5%98%89%e5%b9%b4%e5%8d%8e\/","title":{"rendered":"Luogu P1973. [NOI2011] NOI \u5609\u5e74\u534e"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P1973\">https:\/\/www.luogu.com.cn\/problem\/P1973<\/a><\/li>\n<\/ul>\n<p>O(n4) \u66b4\u529b\u5199\u7684\u597d\u662f\u80fd\u8fc7\u5f97\u3002\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/io&gt;\r\nusing namespace lastweapon;\r\nconst int N = 200 + 1, PN = N*2 + 1;\r\nVI P; int L&#x5B;N], R&#x5B;N], s&#x5B;PN]&#x5B;PN];\r\nint pre&#x5B;PN]&#x5B;N], suf&#x5B;PN]&#x5B;N]; \/\/ \u4e00\u8fb9\u4e3a j\uff0c\u53e6\u4e00\u8fb9\u81f3\u591a\r\nint f&#x5B;PN]&#x5B;PN];\r\nint n, pn;\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    RD(n); REP(i, n) {\r\n        RD(L&#x5B;i], R&#x5B;i]); R&#x5B;i] += L&#x5B;i];\r\n        P.PB(L&#x5B;i]); P.PB(R&#x5B;i]);\r\n    }\r\n    UNQ(P); REP(i, n) {\r\n        L&#x5B;i] = LBD(P, L&#x5B;i]);\r\n        R&#x5B;i] = LBD(P, R&#x5B;i]) - 1;\r\n        s&#x5B;L&#x5B;i]]&#x5B;R&#x5B;i]] += 1;\r\n    }\r\n\r\n    pn = SZ(P)-1; FOR(len, 1, pn) REP(l, pn-len) {\r\n        int r = l + len;\r\n        s&#x5B;l]&#x5B;r] += s&#x5B;l+1]&#x5B;r] + s&#x5B;l]&#x5B;r-1] - s&#x5B;l+1]&#x5B;r-1];\r\n    }\r\n\r\n    REP(i, pn) pre&#x5B;i]&#x5B;0] = s&#x5B;0]&#x5B;i];\r\n    REP(i, pn) suf&#x5B;i]&#x5B;0] = s&#x5B;i]&#x5B;pn-1];\r\n\r\n    REP(i, pn) REP_1(j, s&#x5B;0]&#x5B;i]) REP(k, i) checkMax(pre&#x5B;i]&#x5B;j], max(j &lt;= s&#x5B;0]&#x5B;k] ? pre&#x5B;k]&#x5B;j] + s&#x5B;k+1]&#x5B;i] : 0, j &gt;= s&#x5B;k+1]&#x5B;i] ? pre&#x5B;k]&#x5B;j-s&#x5B;k+1]&#x5B;i]] : 0));\r\n    DWN(i, pn, 0) REP_1(j, s&#x5B;i]&#x5B;pn-1]) DWN(k, pn, i) checkMax(suf&#x5B;i]&#x5B;j], max(j &lt;= s&#x5B;k+1]&#x5B;pn-1] ? s&#x5B;i]&#x5B;k] + suf&#x5B;k+1]&#x5B;j] : 0, j &gt;= s&#x5B;i]&#x5B;k] ? suf&#x5B;k+1]&#x5B;j-s&#x5B;i]&#x5B;k]] : 0));\r\n\r\n    int z = 0; FOR(i, 0, s&#x5B;0]&#x5B;pn-1]+1) checkMax(z, min(i, suf&#x5B;0]&#x5B;i]));\r\n    cout &lt;&lt; z &lt;&lt; endl;\r\n\r\n    REP(i, pn) FOR(j, i, pn) {\r\n        REP(x, s&#x5B;0]&#x5B;i-1]+1) REP(y, s&#x5B;j+1]&#x5B;pn-1] +1) {\r\n            checkMax(f&#x5B;i]&#x5B;j], min(x + s&#x5B;i]&#x5B;j] + y, pre&#x5B;i-1]&#x5B;x] + suf&#x5B;j+1]&#x5B;y]));\r\n        }\r\n    }\r\n\r\n    DWN(len, pn-1, 0) REP(l, pn-len) {\r\n        int r = l + len;\r\n        if (l) checkMax(f&#x5B;l]&#x5B;r], f&#x5B;l-1]&#x5B;r]);\r\n        if (r != pn-1) checkMax(f&#x5B;l]&#x5B;r], f&#x5B;l]&#x5B;r+1]);\r\n    }\r\n\r\n    REP(i, n) cout &lt;&lt; f&#x5B;L&#x5B;i]]&#x5B;R&#x5B;i]] &lt;&lt; endl;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/www.luogu.com.cn\/problem\/P1973 O(n4) \u66b4\u529b\u5199\u7684\u597d\u662f\u80fd\u8fc7\u5f97\u3002\u3002\u3002\u3002 #include &lt;lastweapon\/io&gt; using namespace lastweapon; const int N = 200 + 1, PN = N*2 + 1; VI P; int L&#x5B;N], R&#x5B;N], s&#x5B;PN]&#x5B;PN]; int pre&#x5B;PN]&#x5B;N], suf&#x5B;PN]&#x5B;N]; \/\/ \u4e00\u8fb9\u4e3a j\uff0c\u53e6\u4e00\u8fb9\u81f3\u591a int f&#x5B;PN]&#x5B;PN]; int n, pn; int main() { #ifndef ONLINE_JUDGE freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin); \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout); #endif RD(n); REP(i, n) { RD(L&#x5B;i], R&#x5B;i]); [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_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","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-3023","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-ML","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3023","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=3023"}],"version-history":[{"count":2,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3023\/revisions"}],"predecessor-version":[{"id":3025,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3023\/revisions\/3025"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=3023"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=3023"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=3023"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}