{"id":870,"date":"2023-11-12T17:34:16","date_gmt":"2023-11-12T09:34:16","guid":{"rendered":"http:\/\/ggapa.net:81\/?p=870"},"modified":"2023-11-12T17:36:52","modified_gmt":"2023-11-12T09:36:52","slug":"%e7%8e%af%e4%b8%8a%e6%9c%80%e5%a4%a7%e7%8b%ac%e7%ab%8b%e9%9b%86%e9%97%ae%e9%a2%98","status":"publish","type":"post","link":"http:\/\/ggapa.net:81\/2023\/11\/12\/%e7%8e%af%e4%b8%8a%e6%9c%80%e5%a4%a7%e7%8b%ac%e7%ab%8b%e9%9b%86%e9%97%ae%e9%a2%98\/","title":{"rendered":"\u73af\u4e0a\u6700\u5927\u72ec\u7acb\u96c6\u95ee\u9898"},"content":{"rendered":"<h1>\u73af\u4e0a\u6700\u5927\u72ec\u7acb\u96c6<\/h1>\n<h2>\u9898\u76ee\u63cf\u8ff0<\/h2>\n<p>\u7ed9\u51fa\u4e00\u4e2a\u6709 $n$ \u4e2a\u70b9\u7684\u73af\uff0c\u6bcf\u4e2a\u70b9\u6709\u70b9\u6743 $a_i$\uff0c\u6c42\u6ee1\u8db3\u70b9\u96c6\u5185\u4efb\u4f55\u4e24\u4e2a\u70b9\u5728\u73af\u4e0a\u4e0d\u76f8\u90bb\uff0c\u4e14\u70b9\u6743\u548c\u6700\u5927\u7684\u70b9\u96c6\u7684\u70b9\u6743\u548c\u3002<br \/>\n\u6ce8\u610f\u70b9 $1$ \u548c \u70b9 $n$ \u662f\u76f8\u90bb\u7684\u3002<\/p>\n<h2>\u8f93\u5165\u683c\u5f0f<\/h2>\n<p>\u7b2c\u4e00\u884c\u8f93\u5165\u4e00\u4e2a\u6b63\u6574\u6570 $n$\uff0c\u8868\u793a\u70b9\u7684\u6570\u76ee\u3002<br \/>\n\u7b2c\u4e8c\u884c\u8f93\u5165 $n$ \u4e2a\u4ee5\u7a7a\u683c\u9694\u5f00\u7684\u6574\u6570\uff0c\u4f9d\u6b21\u8868\u793a\u5404\u4e2a\u70b9\u7684\u70b9\u6743 $a_i$\u3002<\/p>\n<h2>\u8f93\u51fa\u683c\u5f0f<\/h2>\n<p>\u8f93\u51fa\u4e00\u884c\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a\u6c42\u5f97\u7684\u6700\u5927\u70b9\u6743\u548c\u3002<\/p>\n<h2>\u6837\u4f8b #1<\/h2>\n<h3>\u6837\u4f8b\u8f93\u5165 #1<\/h3>\n<pre><code>7\n2 -2 8 6 -1 -5 5<\/code><\/pre>\n<h3>\u6837\u4f8b\u8f93\u51fa #1<\/h3>\n<pre><code>13<\/code><\/pre>\n<h2>\u63d0\u793a<\/h2>\n<p>\u5bf9\u4e8e $50\\%$ \u7684\u6570\u636e\u6ee1\u8db3 $n\\le 18$\uff1b<br \/>\n\u5bf9\u4e8e $100\\%$ \u7684\u6570\u636e\u6ee1\u8db3 $2\\le n\\le 10^5,|a_i|\\le 10^9$\u3002<\/p>\n<h1>\u89e3\u9898\u65b9\u6cd5<\/h1>\n<p>\u82e5\u4e0d\u8003\u8651\u73af\uff0c\u6b64\u9898\u7684\u8f6c\u79fb\u65b9\u7a0b\u5982\u4e0b\uff1a<\/p>\n<p><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><mi>f<\/mi><mo stretchy=\"false\">[<\/mo><mi>i<\/mi><mo stretchy=\"false\">]<\/mo><mo stretchy=\"false\">[<\/mo><mn>1<\/mn><mo stretchy=\"false\">]<\/mo><mo>=<\/mo><mi>f<\/mi><mo stretchy=\"false\">[<\/mo><mi>i<\/mi><mo>\u2212<\/mo><mn>1<\/mn><mo stretchy=\"false\">]<\/mo><mo stretchy=\"false\">[<\/mo><mn>0<\/mn><mo stretchy=\"false\">]<\/mo><\/math><br \/>\n<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><mi>f<\/mi><mo stretchy=\"false\">[<\/mo><mi>i<\/mi><mo stretchy=\"false\">]<\/mo><mo stretchy=\"false\">[<\/mo><mn>0<\/mn><mo stretchy=\"false\">]<\/mo><mo>=<\/mo><mo data-mjx-texclass=\"OP\" movablelimits=\"true\">max<\/mo><mo fence=\"false\" stretchy=\"false\">{<\/mo><mi>f<\/mi><mo stretchy=\"false\">[<\/mo><mi>i<\/mi><mo>\u2212<\/mo><mn>1<\/mn><mo stretchy=\"false\">]<\/mo><mo stretchy=\"false\">[<\/mo><mn>1<\/mn><mo stretchy=\"false\">]<\/mo><mo>,<\/mo><mi>f<\/mi><mo stretchy=\"false\">[<\/mo><mi>i<\/mi><mo>\u2212<\/mo><mn>1<\/mn><mo stretchy=\"false\">]<\/mo><mo stretchy=\"false\">[<\/mo><mn>0<\/mn><mo stretchy=\"false\">]<\/mo><mo fence=\"false\" stretchy=\"false\">}<\/mo><\/math><\/p>\n<p>\u5176\u4e2d $f[i][1]$ \u4ee3\u8868\u7b2c $i$ \u4e2a\u5143\u7d20\u8981\u53d6\uff0c$f[i][0]$ \u4ee3\u8868\u7b2c $i$ \u4e2a\u5143\u7d20\u4e0d\u53d6\u3002\u82e5\u7b2c $i$ \u4e2a\u5143\u7d20\u8981\u53d6\uff0c\u5219\u7b2c $i-1$ \u4e2a\u5143\u7d20\u4e0d\u80fd\u53d6\u3002\u82e5\u7b2c $i$ \u4e2a\u5143\u7d20\u4e0d\u53d6\uff0c\u5219\u7b2c $i-1$ \u4e2a\u5143\u7d20\u53ef\u53d6\u53ef\u4e0d\u53d6\u3002\u4ee5\u4e0a\u4fbf\u662f\u8f6c\u79fb\u65b9\u7a0b\u7684\u7531\u6765\u3002<\/p>\n<p>\u82e5\u6309\u7167\u4f20\u7edf\u7684\u5316\u73af\u6210\u94fe\u65b9\u6cd5\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a $O(n^2)$ \u5f88\u660e\u663e\u4e0d\u80fd\u901a\u8fc7\u672c\u9898\uff0c\u4f46\u662f\u6211\u4eec\u53ef\u4ee5\u4ece\u8fd9\u4e2a\u65b9\u6cd5\u5c55\u5f00\u601d\u8003\u3002\u4e3a\u4ec0\u4e48\u8981\u5316\u73af\u6210\u94fe\uff1f\u56e0\u4e3a\u5728\u73af\u91cc\uff0c$1$ \u53f7\u5143\u7d20\u548c $n$ \u53f7\u5143\u7d20\u662f\u9760\u5728\u4e00\u8d77\u7684\uff0c\u82e5 $1$ \u53d6\uff0c\u5219 $n$ \u53f7\u5143\u7d20\u4e0d\u80fd\u53d6\uff0c\u53cd\u4e4b\u4ea6\u7136\u3002\u6211\u4eec\u5c31\u53ef\u4ee5\u5206\u60c5\u51b5\u8fdb\u884c\u52a8\u6001\u89c4\u5212\uff0c\u7b2c\u4e00\u79cd\u60c5\u51b5\u662f\u5f53 $1$ \u53f7\u5143\u7d20\u4e0d\u53d6\u7684\u65f6\uff0c $n$ \u53f7\u5143\u7d20\u53ef\u53d6\u53ef\u4e0d\u53d6\u3002\u7b2c\u4e8c\u79cd\u60c5\u51b5\u662f\u5f53\u7b2c $n$ \u53f7\u5143\u7d20\u53d6\u65f6\uff0c\u5219 $1$ \u53f7\u5143\u7d20\u53ef\u53d6\u53ef\u4e0d\u53d6\u3002<\/p>\n<p>\u4e3a\u4e86\u8fbe\u5230\u6b64\u76ee\u7684\uff0c\u60c5\u51b5\u4e00\u6211\u4eec\u53ef\u4ee5\u5c06 $f[1][0]$ \u7684\u503c\u8bbe\u4e3a $-\\infty$ \uff0c\u60c5\u51b5\u4e8c\u53ef\u4ee5\u5c06 $f[1][1]$ \u7684\u503c\u8bbe\u4e3a $-\\infty$\u3002\u63a5\u7740\u8fdb\u884c\u4e0a\u8ff0\u52a8\u6001\u89c4\u5212\uff0c\u95ee\u9898\u5373\u53ef\u8fce\u5203\u800c\u89e3\u3002<\/p>\n<p><a href=\"https:\/\/www.luogu.com.cn\/record\/134763290\">AC \u4ee3\u7801<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u73af\u4e0a\u6700\u5927\u72ec\u7acb\u96c6 \u9898\u76ee\u63cf\u8ff0 \u7ed9\u51fa\u4e00\u4e2a\u6709 $n$ \u4e2a\u70b9\u7684\u73af\uff0c\u6bcf\u4e2a\u70b9\u6709\u70b9\u6743 $a_i$\uff0c\u6c42\u6ee1\u8db3\u70b9\u96c6\u5185\u4efb\u4f55\u4e24\u4e2a\u70b9\u5728\u73af\u4e0a [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[31],"_links":{"self":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/870"}],"collection":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/comments?post=870"}],"version-history":[{"count":2,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/870\/revisions"}],"predecessor-version":[{"id":873,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/870\/revisions\/873"}],"wp:attachment":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/media?parent=870"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/categories?post=870"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/tags?post=870"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}