{"id":127,"date":"2021-06-18T09:26:29","date_gmt":"2021-06-18T09:26:29","guid":{"rendered":"http:\/\/cirno.fun\/?p=127"},"modified":"2021-06-18T09:26:29","modified_gmt":"2021-06-18T09:26:29","slug":"%e9%a2%98%e8%a7%a3-p1570-%e3%80%90kc%e5%96%9d%e5%92%96%e5%95%a1%e3%80%91-2","status":"publish","type":"post","link":"https:\/\/blog.sssn.tech\/?p=127","title":{"rendered":"\u9898\u89e3 P1570 \u3010KC\u559d\u5496\u5561\u3011"},"content":{"rendered":"\n

\uff0180\u5206\u6b6a\u89e3\u6ce8\u610f<\/h2>\n\n\n\n

\u6211\u4e00\u770b\u8fd9\u9898\u611f\u89c9\u5c31\u662f\u641c\u7d22\u554a\u2026\u524d\u9762\u5927\u4f6c\u90fd\u662f\u4e8c\u5206\uff0c\u8bf4\u5b9e\u8bdd\u6211\u6ca1\u60f3\u5230\uff0c\u9898\u89e3\u4e5f\u6ca1\u4eba\u53d1\u641c\u7d22\u7684\uff08\u4eba\u5bb6\u90fd\u4e8c\u5206\u8fc7\u4e86\u8c01\u7ba1\u4f60\u641c\u7d22<\/del>\uff09<\/p>\n\n\n\n

\u540e\u6765\u8bc1\u5b9e\u4e86\u4e8c\u5206\u662f\u6b63\u89e3\uff0c\u641c\u7d22\u662f\u6b6a\u89e3\u2026\u5177\u4f53\u4ec0\u4e48\u539f\u56e0\u5f85\u4f1a\u4f1a\u8bb2<\/p>\n\n\n\n

\u7b80\u5355\u5206\u6790\u9898\u610f\uff0c\u6211\u4eec\u53ef\u77e5\u5bf9\u4e8e\u6bcf\u4e00\u79cd\u8c03\u6599\u6211\u4eec\u90fd\u53ef\u4ee5\u9009\u6216\u8005\u4e0d\u9009\uff0c\u9009\u5c31\u83b7\u5f97\u4e00\u4e2a\u6536\u76ca\u4e14\u4ed8\u51fa\u4e00\u4e2a\u4ee3\u4ef7\uff0c\u4e0d\u9009\u5c31\u5f53\u65e0\u4e8b\u53d1\u751f<\/p>\n\n\n\n

\u9996\u5148\u60f3\u5230\u662f\u80cc\u5305\uff1f\u4f46\u662f\u672c\u9898\u8ba1\u7b97\u6700\u7ec8\u6536\u76ca\u7684\u65b9\u6cd5\u662f\u6c42\u548c\u540e\u518d\u5546\u2026\u60f3\u4e86\u60f3\u611f\u89c9\u4ee5\u6211\u7684\u6c34\u5e73\u5f88\u4e0d\u53ef\u505aorz<\/p>\n\n\n\n

\u90a3\u5c31\u5c1d\u8bd5\u4e00\u4e0b\u641c\u7d22\u5217\u4e3e\u6bcf\u79cd\u51b3\u7b56\u5427\uff08\u6211\u731c\u6709\u4eba\u8bb0\u4e0d\u4f4f\u6570\u7ec4\u542b\u4e49\uff0c\u4e8e\u662f\u8d34\u5fc3\u7684\u6807\u51fa\u6765hh<\/p>\n\n\n\n

double tim[N],vl[N];\/\/tim\u662f\u82b1\u8d39\u65f6\u95f4\uff0cvl\u662f\u4ef7\u503c\uff08\u597d\u5403\u7a0b\u5ea6\n void dfs(int k,double cst,double del,int c){\n     \/\/\u6b63\u5728\u5904\u7406\u7b2ck\u4e2a\uff0c\u8bdd\u8d39\u65f6\u95f4cst\uff0c\u6536\u76ca\u597d\u5403\u7a0b\u5ea6del\uff0c\u5df2\u7ecf\u9009\u4e86c\u4e2d\u8c03\u6599\n     if(c==m){\/\/\u9009\u597d\u4e86m\u79cd\u5219\u66f4\u65b0\u7b54\u6848\n         ans=max(ans,del\/cst);\n         return;\n     }\n     if(k>n) return;\/\/\u9009\u51fa\u754c\u4e86\n dfs(k+1,cst+tim[k],del+vl[k],c+1);\/\/\u9009\u62e9\u4f1a\u5e26\u6765\u6536\u76ca\u548c\u4ee3\u4ef7\uff0c\u4ee5\u53ca\u9009\u62e9\u6570\u91cf++ dfs(k+1,cst,del,c);\/\/\u4e0d\u9009\u5219\u5f53\u65e0\u4e8b\u53d1\u751f\uff0c\u8003\u8651\u4e0b\u4e00\u4e2a\u51b3\u7b56<\/code>\n }<\/code><\/pre>\n\n\n\n
\u6d4b\u4e86\u6837\u4f8b\uff0c\u611f\u89c9\u81ea\u5df1\u771f\u7684\u5f88\u4e0d\u9519\uff0c\u63d0\u4ea4\u4e00\u770b\uff0c80\u5206<\/p>\n\n\n\n
\u6bd5\u7adf\u662f\u7eaf\u66b4\u529b\u505a\u6cd5..<\/del><\/p>\n\n\n\n
\u4ee5\u4e0b\u662f\u6211\u5bf9\u4e8e\u526a\u679d\u7684\u4e00\u4e9b\u601d\u8003\u548c\u5931\u8d25\u7ecf\u5386\uff0c\u7531\u4e8e\u592a\u5f31\u5c1d\u8bd5\u51e0\u6b21\u5e76\u4e0d\u6210\u529f\uff0c\u6b22\u8fce\u795e\u725b\u6307\u70b9\u4e00\u4e0borz<\/p>\n\n\n\n
\u60f3\u4e86\u60f3\uff0c\u6709\u4e00\u79cd\u526a\u679d\u7b56\u7565\u662f<\/p>\n\n\n\n
\u7528\u524d\u7f00\u548c\u6570\u7ec4\u8bb0\u4e0b\u6bcf\u4e2a\u8c03\u6599\u7684\u6536\u76ca\uff0c\u5728\u5bf9\u4e00\u4e2a\u51b3\u7b56\u8fdb\u884c\u5206\u6790\u65f6\uff0c\u5982\u679c\u540e\u9762\u7684\u8c03\u6599\u5168\u9009\u4e5f\u4e0d\u5982\u5f53\u524d\u7684\u72b6\u6001\u4f18\uff0c\u5219\u8df3\u8fc7\u8fd9\u4e2a\u51b3\u7b56<\/h2>\n\n\n\n
void dfs(int k,double cst,double del,int c){\n     \/\/\u6b63\u5728\u5904\u7406\u7b2ck\u4e2a\uff0c\u8bdd\u8d39\u65f6\u95f4cst\uff0c\u6536\u76ca\u597d\u5403del\uff0c\u5df2\u7ecf\u9009\u4e86c\n     if(cst!=0 && (del+s[n]-s[k-1])\/cst<=del\/cst)return;\n     if(c==m){\n          \/\/cout<<del<<':'<<cst<<endl;\n          ans=max(ans,del\/cst);\n          return;\n     }\n     if(k>n)    return;\n     dfs(k+1,cst+tim[k],del+vl[k],c+1);\n     dfs(k+1,cst,del,c);\n }<\/code><\/pre>\n\n\n\n
\u6d4b\u4e86\u6837\u4f8b\uff0c\u611f\u89c9\u81ea\u5df1\u771f\u7684\u5f88\u4e0d\u9519<\/del>\uff0c\u4ea4\u4e0a\u53bb\u6d4b\uff0c\u8fd8\u662fT<\/p>\n\n\n\n
orz<\/p>\n\n\n\n
\u5176\u5b9e\u4ed4\u7ec6\u60f3\u60f3\u5c31\u80fd\u77e5\u9053\u8fd9\u79cd\u72b6\u6001\u8fc7\u4e8e\u6781\u7aef\uff0c\u867d\u7136\u6b63\u786e\u4f46\u5e76\u4e0d\u80fd\u526a\u6389\u80fd\u5f71\u54cd\u7b97\u6cd5\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u679d\u6761<\/strong>\uff0c\u4e8e\u662f\u6211\u4e0d\u4fe1\u90aa\uff0c\u540e\u9762\u603b\u4e0d\u80fd\u6536\u76ca\u90fd\u662f1\u5427\uff0c\u6211\u60f3\u727a\u7272\u4e00\u5b9a\u7684\u6b63\u786e\u7387\u6765\u6c42\u80fd\u5361\u8fdb1s\u65f6\u9650\uff08\u4ec0\u4e48\u65f6\u5019\u53d8\u6210\u8c03\u53c2\u95ee\u9898\u4e86\uff09<\/p>\n\n\n\n
if(cst!=0 && (del+s[n]-s[k-1])\/cst<=del\/(cst+10000))return;<\/code><\/pre>\n\n\n\n
\u6d4b\u4e86\u6837\u4f8b\uff0c\u611f\u89c9\u81ea\u5df1\u771f\u7684\u5f88\u4e0d\u9519<\/del>\uff0c\u4ea4\u4e0a\u53bb\u6d4b\uff0c\u8fd8\u662fT<\/p>\n\n\n\n
orz<\/p>\n\n\n\n
\u5176\u5b9e\u4ed4\u7ec6\u60f3\u60f3\u5c31\u80fd\u77e5\u9053\u8fd9\u79cd\u72b6\u6001\u8fc7\u4e8e\u6781\u7aef\uff0c\u867d\u7136\u6b63\u786e\u4f46\u5e76\u4e0d\u80fd\u526a\u6389\u80fd\u5f71\u54cd\u7b97\u6cd5\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u679d\u6761<\/strong>\uff0c\u4e8e\u662f\u6211\u4e0d\u4fe1\u90aa\uff0c\u540e\u9762\u603b\u4e0d\u80fd\u6536\u76ca\u90fd\u662f1\u5427\uff0c\u6211\u60f3\u727a\u7272\u4e00\u5b9a\u7684\u6b63\u786e\u7387\u6765\u6c42\u80fd\u5361\u8fdb1s\u65f6\u9650\uff08\u4ec0\u4e48\u65f6\u5019\u53d8\u6210\u8c03\u53c2\u95ee\u9898\u4e86\uff09<\/p>\n\n\n\n
if(cst!=0 && (del+s[n]-s[k-1])\/cst<=del\/(cst+10000))return;<\/code><\/pre>\n\n\n\n
\u526a\u6389\u4e86\u5417\uff1f\u526a\u6389\u4e86\u5417\uff1f\u5e76\u6ca1\u6709<\/p>\n\n\n\n
\u4e0b\u8f7d<\/del>\u5206\u6790\u6570\u636e\u8303\u56f4\u540e\u731b\u7136\u53d1\u73b0\uff0c\u5927\u6570\u636e\u70b9\u7684\u8bdd\u8d39\u90fd\u662f1w+\u2026\u90a3\u4e48\u53ef\u4ee5\u77e5\u9053\u8fd9\u79cd\u526a\u679d\u7b56\u7565\u4e0d\u53ef\u80fd\u6709\u6548\u4e86<\/p>\n\n\n\n
\u518d\u5206\u6790\u4e00\u6ce2\uff0c\u4f3c\u4e4e\u53ef\u4ee5\u8fd9\u4e48\u526a\u4e00\u4e0b\uff1a<\/p>\n\n\n\n
\u5bf9\u4e8e\u4e00\u4e2a\u72b6\u6001\uff0c\u5982\u679c\u5269\u4e0b\u7684\u5168\u9009\u540e\u9762\u6536\u76ca\u6700\u5927\u7684\u8c03\u6599\u4e14\u4ee3\u4ef7\u53ea\u52a0\u4e00\u4e2a\u8f83\u5c0f\u503c\uff08\u53c8\u8c03\u53c2\u8349<\/del>\uff09\u8fd8\u4e0d\u5982\u5f53\u524d\u4f18\uff0c\u5219\u53ef\u4ee5\u4e0d\u9009<\/h4>\n\n\n\n
\u5206\u6790\u5b8c\u53d1\u73b0\uff0c\u4f3c\u4e4e\u53ef\u4ee5\u7528 $O(n^2)$ \u7684\u6548\u7387\u7ef4\u62a4\u4e00\u4e2a\u533a\u95f4\u6700\u503c\uff0c\u60a8\u60f3\u7528\u7ebf\u6bb5\u6570+\u671f\u671b\u4e5f\u884corz<\/del>\uff0c\u5b9e\u73b0\u8fd9\u4e2a\u526a\u679d\uff0c\u4f46\u662f\u7ecf\u8fc7\u66b4\u529b\u5206\u6790<\/del>\u5927\u6982\u53ef\u4ee5\u4f30\u8ba1\uff0c\u7531\u4e8e\u526a\u679d\u6839\u672c\u601d\u60f3\u6ca1\u53d8\uff0c\u6548\u7387\u4e5f\u6ca1\u6709\u5728\u65f6\u95f4\u590d\u6742\u5ea6\u4e0a\u7684\u63d0\u5347<\/strong>\uff0c\u52a0\u4e4b\u8001\u4ee3\u7801\u8dd1\u5b8c\u5f97\u5feb1min\uff0c\u4e8e\u662f\u679c\u65ad\u653e\u5f03\uff08\u7136\u800c\u5f97\u5206\u7684\u6570\u636e\u70b9\u90fd\u662f2ms\uff0c3ms\uff0c\u53ef\u89c1\u6570\u636e\u6c34\u7684\u53ef\u4ee5hh<\/del>\uff09<\/p>\n\n\n\n
\u8003\u573a\u4e0a\u7684\u8bdd\uff0c\u6211\u5c31\u62ff\u90e8\u5206\u5206\u6eda\u7c97\u4e86qwq<\/p>\n\n\n\n
\u4ee5\u4e0a\u662f\u6211\u5bf9\u4e8e\u672c\u9898\u526a\u679d\u7684\u4e00\u70b9\u70b9\u5c0f\u601d\u8003\u548c\u5c1d\u8bd5\uff0c\u5982\u679c\u4f60\u6709\u66f4\u597d\u7684\u526a\u679d\u7b56\u7565\u8bf7\u548c\u6211\u4e00\u8d77\u8ba8\u8bba\uff0c\u8ba9\u672c\u9898\u6709\u4e00\u4e2a\u6b6a\u89e3AC\u5427\uff08\u7b11<\/p>\n","protected":false},"excerpt":{"rendered":"
\uff0180\u5206\u6b6a\u89e3\u6ce8\u610f \u6211\u4e00\u770b\u8fd9\u9898\u611f\u89c9\u5c31\u662f\u641c\u7d22\u554a\u2026\u524d\u9762\u5927\u4f6c\u90fd\u662f\u4e8c\u5206\uff0c\u8bf4\u5b9e\u8bdd\u6211\u6ca1\u60f3\u5230\uff0c\u9898 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-127","post","type-post","status-publish","format-standard","hentry","category-2"],"_links":{"self":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/127","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=127"}],"version-history":[{"count":0,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/127\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=127"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=127"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=127"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}