{"id":993,"date":"2019-02-21T22:13:47","date_gmt":"2019-02-21T14:13:47","guid":{"rendered":"https:\/\/0self.mnihyc.com\/blog\/?p=993"},"modified":"2020-02-09T03:01:13","modified_gmt":"2020-02-08T19:01:13","slug":"%e6%b5%85%e8%b0%88%e6%96%9c%e7%8e%87%e4%bc%98%e5%8c%96-%e6%88%aa%e8%b7%9d%e4%bc%98%e5%8c%96","status":"publish","type":"post","link":"https:\/\/0self.mnihyc.com\/blog\/archives\/993","title":{"rendered":"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316"},"content":{"rendered":"<h1 style=\"text-align: center;\">\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316<\/h1>\n<p>\u6700\u8fd1<del>\uff08\u4e24\u4e2a\u6708\u524d\uff09<\/del>\u5b66\u4e60\u4e86<strong>\u659c\u7387\u4f18\u5316<\/strong> \u2014\u2014 \u4e00\u79cd\u4f18\u5316 <strong>1D1D<\/strong> \u52a8\u6001\u89c4\u5212<strong>\u8f6c\u79fb\u65b9\u7a0b<\/strong>\u7684\u9ad8\u6548\u65b9\u6cd5\uff0c\u5728\u8f83\u9ad8\u96be\u5ea6\u7684\u6bd4\u8d5b\u4e2d\u662f\u4e00\u79cd\u5341\u5206\u5e38\u89c1\u7684 DP \u4f18\u5316\u624b\u6bb5\u3002\u9274\u4e8e\u6211\u4e4b\u524d<del>\uff08\u4e00\u5e74\u524d\uff09<\/del>\u4e5f\u7a0d\u5fae\u63a5\u89e6\u8fc7\u4e00\u70b9\u76f8\u5173\u65b9\u9762\u7684\u77e5\u8bc6\uff0c\u4f46\u662f\u5b8c\u5168\u6ca1\u6709\u641e\u61c2\uff08\u592a\u83dc\u4e86\uff09\uff0c\u6700\u8fd1<del>\uff08\u4e24\u4e2a\u6708\u524d\uff09<\/del>\u518d\u914d\u5408 orzCJK\u5b66\u957f \u63d0\u51fa\u7684<strong>\u622a\u8ddd\u4f18\u5316<\/strong>\u7684\u601d\u60f3\u7406\u5ff5\u624d\u5bf9\u4e8e\u659c\u7387\u4f18\u5316\u95ee\u9898\u6709\u4e86\u6df1\u523b\u7684\u89c1\u89e3\uff0c\u6545\u5728\u8fd9\u91cc\u5bf9 orzCJK\u5b66\u957f \u7684 <a href=\"https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/\u659c\u7387\u4f18\u5316_\u622a\u8ddd\u4f18\u5316\uff01.pdf\"><span style=\"color: #0000ff;\">\u659c\u7387\u4f18\u5316_\u622a\u8ddd\u4f18\u5316\uff01.pdf<\/span><\/a> \u8fdb\u884c\u8be6\u7ec6\u7684\u89e3\u91ca\u8bf4\u660e\u3002<\/p>\n<p>&nbsp;<\/p>\n<p>\u9996\u5148\uff0c1D1D \u6307\u7684\u662f\u72b6\u6001\u6570 \\(O(n)\\) \u8f6c\u79fb \\(O(n)\\) \u7684\u52a8\u6001\u89c4\u5212\u65b9\u7a0b\u3002\u5728\u6ee1\u8db3\u4e00\u4e9b\u6761\u4ef6\u7684\u60c5\u51b5\u4e0b\uff0c\u659c\u7387\u4f18\u5316\u53ef\u4ee5\u5c06\u8f6c\u79fb\u7684 \\(O(n)\\) \u4f18\u5316\u81f3 \\(O(logn)\\) \u751a\u81f3\u53ef\u4ee5\u5230 \\(O(1)\\) \u3002\u8fd9\u6837\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u7531 \\(O(n^2)\\) \u53d8\u4e3a \\(O(nlogn)\\) \u751a\u81f3\u662f \\(O(n)\\) \uff0c\u53ef\u89c1\u659c\u7387\u4f18\u5316\u7684\u9ad8\u6548\u6027\u3002<\/p>\n<p>\u5982\u679c\u6709\u4e00\u4e2a DP \u65b9\u7a0b\u7684\u67d0\u4e2a\u72b6\u6001\u4e3a \\(f_i\\) \uff0c\u5982\u679c\u80fd\u63a8\u5bfc\u51fa\u7c7b\u4f3c\u4e8e \\(f_i=c_i + \\min\\limits_{j&lt;i \\land \\cdots}{\\{a_j + w_i \\cdot b_j\\}}\\) \uff0c\u90a3\u4e48\u8fd9\u4e2a\u8f6c\u79fb\u65b9\u7a0b\u5c31\u53ef\u4ee5\u4f7f\u7528\u659c\u7387\u4f18\u5316\u8fdb\u884c\u4f18\u5316\u3002<\/p>\n<p>\u7136\u800c\u666e\u901a\u7684\u8f6c\u79fb\u65b9\u7a0b\u5e76\u6ca1\u6709\u4ec0\u4e48\u7279\u6b8a\u7684\u5730\u65b9\uff0c\u4f7f\u7528\u7ecf\u5178\u7684\u65b9\u6cd5<del>\uff08\u6211\u4e5f\u4e0d\u4f1a\uff09<\/del>\u7565\u663e\u7e41\u7410\uff0c\u6240\u4ee5\u73b0\u5728\u6211\u4eec\u8981\u8d4b\u4e88\u5b83\u4ee5<strong>\u51e0\u4f55\u610f\u4e49<\/strong>\u3002\uff08\u65f6\u523b\u6ce8\u610f\uff0c\u8fd9\u4e2a\u8f6c\u79fb\u65b9\u7a0b\u7684<strong>\u610f\u4e49<\/strong>\u662f\u5bf9\u4e8e\u4e00\u4e2a \\(i\\) \u5728 \\(j &lt; i\\) \u8303\u56f4\u5185\u5bfb\u627e \\(j\\) \u4f7f \\(a_j + w_i \\cdot b_j\\)\uff09\u6700\u5c0f\u3002\uff09<\/p>\n<p>\u6362\u4e00\u4e0b\u53d8\u91cf\u540d\uff0c\u8bbe \\(y_j=a_j, k_i=-w_i, x_j=b_j\\) \uff0c\u90a3\u4e48\u8fd9\u6837\u9700\u8981\u6700\u5c0f\u5316\u7684\u5f0f\u5b50\u5c31\u53d8\u4e3a \\(\\underbrace{a_j}_{y_j} &#8211; \\underbrace{-w_i}_{k_i} \\cdot \\underbrace{b_j}_{x_j}\\) \u3002\u8fd9\u4e0d\u5c31\u662f<strong>\u622a\u8ddd \\(b = y &#8211; kx\\) <\/strong>\u5417\uff1f\uff01\uff01\u4e5f\u5c31\u662f\u8bf4\uff0c\u8981\u6700\u5c0f\u5316\u7684\u5c31\u662f\u4e00\u6761<strong>\u8fc7 \\(\\left(x_j, y_j\\right)\\)<\/strong> \u4e14<strong>\u659c\u7387\u4e3a \\(k_i\\)<\/strong> \u7684\u76f4\u7ebf\u7684<strong>\u622a\u8ddd<\/strong>\uff01<\/p>\n<p>\u6362\u53e5\u8bdd\u8bf4\uff0c\u628a\u6240\u6709\u5bf9\u4e8e\u5f53\u524d \\(i\\) \u53ef\u8f6c\u79fb\u7684 \\(j\\) \u90fd\u8868\u793a\u4e3a\u4e8c\u7ef4\u5e73\u9762\u4e0a\u7684<strong>\u4e00\u4e2a\u70b9 \\(p_j=\\left(x_j, y_j\\right)\\)<\/strong> \uff0c\u6211\u4eec\u9700\u8981\u505a\u7684\u5c31\u662f\u5728\u6240\u6709\u8fd9\u6837\u7684\u70b9\u4e2d\uff0c\u627e\u5230\u4e00\u4e2a\u70b9\uff0c<strong>\u4f7f\u7ecf\u8fc7\u5b83\u4e14<span style=\"text-decoration: underline;\">\u659c\u7387\u4e3a \\(k_i\\)<\/span> \u7684\u76f4\u7ebf\u7684<span style=\"text-decoration: underline;\">\u622a\u8ddd<\/span>\u6700\u5c0f<\/strong>\uff01\u8fd9\u4e5f\u662f\u4e3a\u4ec0\u4e48\u659c\u7387\u4f18\u5316\u5c31\u662f\u622a\u8ddd\u4f18\u5316\u7684\u539f\u56e0\uff0c\u5b83\u5176\u5b9e\u4f18\u5316\u7684\u662f\u622a\u8ddd\uff01<\/p>\n<p>\u73b0\u5728\u60f3\u8c61\u4e00\u6761<strong>\u659c\u7387\u56fa\u5b9a<\/strong>\u7684\u76f4\u7ebf<strong>\u4ece\u4e0b\u5f80\u4e0a<\/strong>\u5e73\u79fb\uff0c\u5f53\u5b83<strong>\u7b2c\u4e00\u6b21<\/strong>\u7ecf\u8fc7\u67d0\u4e2a\u70b9 \\(p_j\\) \u65f6\uff0c\u8fd9\u65f6\u7684<strong>\u622a\u8ddd<\/strong>\u80af\u5b9a\u53d6\u5230\u6700\u5c0f\u503c\u3002\u90a3\u4e48\u8fd9\u4e2a\u70b9 \\(p_j\\) \u5728\u4ec0\u4e48\u5730\u65b9\u5462\uff1f\u663e\u7136\uff0c\u5b83\u4f1a\u5728\u6240\u6709 \\(p\\) \u7ec4\u6210\u7684<span style=\"text-decoration: underline;\"><strong>\u4e0b\u51f8\u58f3<\/strong><\/span>\u4e0a\u3002<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-995\" src=\"https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope.png\" alt=\"\" width=\"606\" height=\"404\" srcset=\"https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope.png 606w, https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope-300x200.png 300w\" sizes=\"auto, (max-width: 606px) 100vw, 606px\" \/><\/p>\n<p>\u90a3\u4e48\u73b0\u5728\u53ea\u8981\u7ef4\u62a4\u8fd9\u4e2a\u4e0b\u51f8\u58f3\uff0c\u6bcf\u6b21\u5728\u4e0a\u9762\u627e\u70b9\u4f7f\u5f97\u622a\u8ddd\u6700\u5c0f\uff0c\u62ff\u6765\u66f4\u65b0 \\(f_i\\) \u540e\u628a \\((x_i, y_i)\\) \u4e5f\u52a0\u5165\u4e0b\u51f8\u58f3\u5373\u53ef\u3002<\/p>\n<p>\u5728\u8fd9\u91cc\uff0c\u7ef4\u62a4\u8fd9\u4e2a\u51f8\u58f3\u7684\u60c5\u51b5\u5206\u4e3a\u4e09\u79cd\uff1a<\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>\n<h3><span style=\"font-size: 24px;\"><strong>1\uff0c\\(x_j\\) \u548c \\(k_i\\) \u5747\u5355\u8c03<\/strong><\/span><\/h3>\n<\/li>\n<\/ul>\n<p>\u8fd9\u662f\u6700\u7b80\u5355\u7684\u60c5\u51b5\u3002\u7ef4\u62a4\u51f8\u58f3\u65e0\u975e\u5c31\u662f\u7ef4\u62a4\u4e24\u4e2a\u64cd\u4f5c\u2014\u2014<strong>\u67e5\u8be2<\/strong>\u548c<strong>\u52a0\u5165<\/strong>\u3002<\/p>\n<p>\u9996\u5148\u8003\u8651\u5982\u4f55\u627e\u5230\u6700\u4f18\u7684\u70b9\u4f7f\u659c\u7387\u56fa\u5b9a\u4e14\u7ecf\u8fc7\u5b83\u7684\u76f4\u7ebf\u7684\u622a\u8ddd\u6700\u5c0f\u3002\u56e0\u4e3a\u8be2\u95ee\u7684<strong>\u659c\u7387<\/strong> \\(k_i\\) \u662f<strong>\u5355\u8c03<\/strong>\u7684\uff08\u5728\u8fd9\u91cc\u5047\u8bbe\u5b83\u5355\u8c03\u9012\u589e\uff09\uff0c\u6240\u4ee5\u6bcf\u6b21\u627e\u7684\u70b9<strong>\u4e0d\u53ef\u80fd<\/strong>\u5728\u4e0a\u4e00\u6b21\u627e\u7684\u70b9\u7684<strong>\u5de6\u4fa7<\/strong>\uff0c\u8fd9\u662f\u56e0\u4e3a<strong>\u4e0b\u51f8\u58f3<\/strong>\u4e0a\u4e24\u70b9\u4e4b\u95f4\u7684<strong>\u659c\u7387<\/strong>\u4e5f\u662f<strong>\u5355\u589e<\/strong>\u7684\uff0c\u67e5\u8be2\u7684\u659c\u7387\u589e\u5927\u610f\u5473\u7740\u6700\u4f18\u70b9\u53ea\u53ef\u80fd\u5411\u53f3\u79fb\u52a8\u3002<\/p>\n<p>\u6240\u4ee5\u53ef\u4ee5\u5f97\u5230\u4e00\u79cd\u5904\u7406\u65b9\u6cd5\uff0c\u5982\u679c\u961f\u5934\u7684<strong>\u524d\u4e24\u4e2a\u70b9<\/strong>\u8fde\u6210\u7684\u76f4\u7ebf\u7684\u659c\u7387 \u6bd4 \u5f53\u524d\u67e5\u8be2\u7684\u659c\u7387 \\(k_i\\) \u8fd8<span style=\"text-decoration: underline;\"><strong>\u5c0f<\/strong><\/span>\uff0c\u90a3\u4e48\u961f\u5934\u7684\u90a3\u4e2a\u70b9\u80af\u5b9a\u662f\u53d6\u4e0d\u5230\u4e86\uff08\u5982\u4e0b\u56fe\uff09\uff0c\u56e0\u4e3a\u8fd9\u6761\u76f4\u7ebf\u4f1a\u5728\u5230\u8fbe\u7b2c\u4e00\u4e2a\u70b9\u4e4b\u524d<strong>\u5148\u5230\u8fbe\u7b2c\u4e8c\u4e2a\u70b9<\/strong>\uff0c\u6240\u4ee5\u5f39\u51fa\u961f\u5934\u5143\u7d20\u76f4\u5230\u6ee1\u8db3\u6761\u4ef6\uff0c\u8fd9\u6837\u5c31\u53ef\u4ee5\u653e\u5fc3\u7684<strong>\u53d6\u961f\u5934\u5143\u7d20<\/strong>\u4f5c\u4e3a\u6700\u4f18\u70b9\u8d21\u732e\u7ed9 \\(i\\) \u3002<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-997\" src=\"https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope-2.png\" alt=\"\" width=\"606\" height=\"404\" srcset=\"https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope-2.png 606w, https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope-2-300x200.png 300w\" sizes=\"auto, (max-width: 606px) 100vw, 606px\" \/><\/p>\n<p>\u540c\u7406\uff0c\u56e0\u4e3a\u52a0\u5165\u7684\u70b9\u7684 \\(x_j\\) \u4e5f\u662f<strong>\u5355\u8c03<\/strong>\u7684\uff08\u5728\u8fd9\u91cc\u5047\u8bbe\u5b83\u5355\u8c03\u9012\u589e\uff09\uff0c\u6240\u4ee5\u5982\u679c<strong>\u961f\u5c3e\u4e24\u4e2a\u70b9<\/strong>\u8fde\u6210\u7684\u76f4\u7ebf\u7684\u659c\u7387 \u6bd4 <strong>\u6700\u540e\u4e00\u4e2a\u70b9\u548c\u5f53\u524d\u9700\u8981\u52a0\u5165\u7684\u70b9<\/strong>\u8fde\u6210\u7684\u7684\u76f4\u7ebf\u7684\u659c\u7387\u8fd8<span style=\"text-decoration: underline;\"><strong>\u5927<\/strong><\/span>\uff0c\u8bf4\u660e\u56fe\u5f62\u51f9\u8fdb\u53bb\u4e86\uff08\u5982\u4e0b\u56fe\uff09\uff0c\u7531\u4e8e\u7ef4\u62a4\u7684\u662f\u4e0b\u51f8\u58f3\uff0c\u6240\u4ee5\u9700\u8981\u628a\u961f\u5c3e\u5143\u7d20\u5f39\u51fa\u76f4\u5230\u6ee1\u8db3\u6761\u4ef6\uff0c\u6700\u540e\u518d\u628a\u5f53\u524d\u70b9\u52a0\u5165\u3002<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1004\" src=\"https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope-1.png\" alt=\"\" width=\"606\" height=\"241\" srcset=\"https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope-1.png 606w, https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope-1-300x119.png 300w\" sizes=\"auto, (max-width: 606px) 100vw, 606px\" \/><\/p>\n<p>\u8fd9\u6837\u7ef4\u62a4\u8fd9\u4e2a\u5355\u8c03\u961f\u5217\u5c31\u662f \\(O(n)\\) \u7684\uff0c\u603b\u65f6\u95f4\u590d\u6742\u5ea6 \\(O(n)\\) \u3002<\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>\n<h3><span style=\"font-size: 24px;\"><strong>2\uff0c\u53ea\u6709 \\(x_j\\) \u5355\u8c03<\/strong><\/span><\/h3>\n<\/li>\n<\/ul>\n<p>\\(x_j\\) \u662f\u5355\u8c03\u7684\uff0c\u610f\u5473\u7740\u4ecd\u7136\u53ef\u4ee5\u6309\u7167\u4e0a\u9762\u7684\u65b9\u6cd5\u52a0\u5165\u4e00\u4e2a\u70b9\u3002\u90a3\u4e48\u67e5\u8be2\u5462\uff1f\u67e5\u8be2\u7684 \\(k_i\\) \u4e0d\u662f\u5355\u8c03\u7684\uff0c\u8fd9\u5c31\u610f\u5473\u7740<strong>\u4e0d\u80fd<\/strong>\u50cf\u4e4b\u524d\u4e00\u6837\u5f39\u51fa\u961f\u5934\u5143\u7d20\u6765\u627e\u5230\u6700\u4f18\u70b9\uff0c\u56e0\u4e3a\u6700\u4f18\u70b9<strong>\u5931\u53bb<\/strong>\u4e86\u4e00\u4e2a\u6027\u8d28\u2014\u2014\u53ea\u4f1a\u5355\u8c03\u79fb\u52a8\u3002\uff08\u5373\u8fd9\u6b21\u7684\u6700\u4f18\u70b9\u53ef\u80fd\u5728\u4e0a\u4e00\u4e2a\u6700\u4f18\u70b9\u7684\u5de6\u8fb9\u3002\uff09<\/p>\n<p>\u91cd\u65b0\u8003\u8651\u5982\u4f55\u627e\u5230\u8fd9\u4e2a\u6700\u4f18\u70b9\u3002<\/p>\n<p>\u6ce8\u610f\u5230\u7ef4\u62a4\u7684<strong>\u4e0b\u51f8\u58f3<\/strong>\u4e0a\u6240\u6709\u76f4\u7ebf\u7684<strong>\u659c\u7387<\/strong>\u90fd\u662f<strong>\u5355\u8c03\u9012\u589e<\/strong>\u7684\u3002\u8bbe\u6b64\u65f6\u8fd9\u6761\u76f4\u7ebf\u7684\u659c\u7387\u4e3a \\(k\\) \uff0c\u6700\u4f18\u70b9\u4e3a \\(p_j\\)\uff0c \\(p_j\\) \u5230\u51f8\u58f3\u7684\u4e0a\u4e00\u4e2a\u70b9\u7684\u76f4\u7ebf\u7684\u659c\u7387\u4e3a \\(k_1\\) \uff0c\\(p_j\\) \u5230\u51f8\u58f3\u7684\u4e0b\u4e00\u4e2a\u70b9\u7684\u76f4\u7ebf\u7684\u659c\u7387\u4e3a \\(k_2\\) \uff0c<strong>\u90a3\u4e48 \\(k \\in [k_1, k_2]\\)<\/strong> \uff08\u5982\u4e0b\u56fe\uff09\u3002\u6240\u4ee5\u53ef\u4ee5\u5728\u51f8\u58f3\u4e0a<strong><span style=\"text-decoration: underline;\">\u4e8c\u5206<\/span>\u659c\u7387<\/strong>\uff0c\u627e\u5230<strong>\u6bd4\u5f53\u524d\u659c\u7387\u5927<\/strong>\u7684\u76f4\u7ebf\u4e2d<span style=\"text-decoration: underline;\"><strong>\u659c\u7387<\/strong><strong>\u6700\u5c0f<\/strong><\/span>\u7684\u76f4\u7ebf\uff0c\u7528\u5b83\u7684<strong>\u5de6\u7aef\u70b9<\/strong>\u6765\u8d21\u732e\u7b54\u6848\u3002<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1005\" src=\"https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope-3.png\" alt=\"\" width=\"606\" height=\"332\" srcset=\"https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope-3.png 606w, https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope-3-300x164.png 300w\" sizes=\"auto, (max-width: 606px) 100vw, 606px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>\u8fd9\u6837\u52a0\u5165\u70b9\u4ecd\u662f \\(O(1)\\) \uff0c\u67e5\u8be2\u5c31\u53d8\u6210 \\(O(logn)\\) \u4e86\uff0c\u603b\u65f6\u95f4\u590d\u6742\u5ea6 \\(O(nlogn)\\) \u3002<\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>\n<h3><span style=\"font-size: 24px;\"><strong>3\uff0c\\(x_j\\) \u548c \\(k_i\\) \u90fd\u4e0d\u5355\u8c03<\/strong><\/span><\/h3>\n<\/li>\n<\/ul>\n<p>\u67e5\u8be2\u7684 \\(k_i\\) \u4e0d\u5355\u8c03\u8fd8\u53ef\u4ee5\u4e8c\u5206\u591a\u4e2a \\(O(log)\\) \u597d\u8bf4\uff0c\u4f46\u662f\u8fd9\u52a0\u5165\u7684 \\(x_j\\) \u90fd\u4e0d\u5355\u8c03\u4e86\uff0c\u770b\u8d77\u6765\u4f3c\u4e4e\u7ef4\u62a4\u8fd9\u4e2a\u51f8\u58f3\u7684\u590d\u6742\u5ea6\u5c31\u4e0a\u53bb\u4e86\u3002<del>\u54e6\u8c41\uff0c\u5b8c\u86cb\uff0c\u8981\u5199 Splay \u7ef4\u62a4\u4e0b\u51f8\u58f3\u4e86\u3002<\/del>\u5176\u5b9e\u5e76\u4e0d\u7136\uff0c\u8fd9\u4e2a\u65f6\u5019\u53ea\u9700\u8981\u7528\u5230\u4e00\u79cd\u795e\u5947\u7684\u5206\u6cbb\u7b97\u6cd5 \u2014\u2014 <strong>CDQ\u5206\u6cbb<\/strong>\u3002<\/p>\n<p>\u56de\u987e\u4e00\u4e0b\u4e0a\u9762\u659c\u7387\u4f18\u5316\u7684\u5199\u6cd5\uff1a\u628a\u53ef\u4ee5\u5b9e\u73b0\u628a\u4e00\u4e2a\u70b9\u52a0\u5165\u5355\u8c03\u961f\u5217\u7684\u64cd\u4f5c\u662f\u56e0\u4e3a<strong><span style=\"text-decoration: underline;\">\u52a0\u5165<\/span>\u7684 \\(x_j\\)<\/strong> \u662f\u5355\u8c03\u7684\uff0c\u53ef\u4ee5\u53d6\u961f\u5934\u5143\u7d20\u4e3a\u6700\u5c0f\u503c\u662f\u56e0\u4e3a<strong><span style=\"text-decoration: underline;\">\u8be2\u95ee<\/span>\u7684<\/strong>\u659c\u7387 <strong>\\(k_i\\)<\/strong> \u662f\u5355\u8c03\u7684\u3002CDQ\u5206\u6cbb\u5c31\u662f\u7262\u7262\u6293\u4f4f\u8fd9\u4e24\u70b9\u8fdb\u884c\u64cd\u4f5c\u7684\u3002<\/p>\n<p>\u56e0\u4e3a\u662f\u5206\u6cbb\uff0c\u6240\u4ee5\u8981\u6709\u4e00\u4e2a\u5206\u6cbb\u533a\u95f4 \\([l, r]\\) \u8868\u793a<strong>\u7528 \\([l, mid]\\) \u4e2d\u6240\u6709\u70b9<\/strong>\u7684\u4fe1\u606f\u53bb<strong>\u66f4\u65b0 \\((mid, r]\\) <\/strong>\u7684\u6700\u5c0f\u503c\uff08\u53ef\u4ee5\u795e\u5947\u5730\u8bc1\u660e\u8fd9\u6837\u505a\u53ef\u4ee5\u4e0d\u9057\u6f0f\u66f4\u65b0\u6240\u6709\u7684\u60c5\u51b5\uff09\u3002\u90a3\u4e48\u5982\u4f55\u5feb\u901f\u505a\u5230\u8fd9\u4e2a\u66f4\u65b0\u64cd\u4f5c\u5462\uff1f\uff1f\uff1f\u5f88\u7b80\u5355\uff0c\u53ea\u9700\u8981\u628a \\([l, mid]\\) \u4e2d\u7684\u70b9<strong>\u6309\u7167 \\(x\\) \u6392\u5e8f<\/strong>\uff0c\\((mid, r]\\) \u4e2d\u7684\u5143\u7d20\u6309\u7167<strong>\u659c\u7387 \\(k\\) \u6392\u5e8f<\/strong>\uff0c\u8fd9\u6837\u5c31\u53ef\u4ee5\u6309\u7167\u4e0a\u9762\u7684\u659c\u7387\u4f18\u5316\u7684\u5199\u6cd5\u7ef4\u62a4\u4e00\u4e2a\u5355\u8c03\u961f\u5217\u53bb\u66f4\u65b0\u4e86\u3002<\/p>\n<p>\u76f4\u63a5\u5728\u91cc\u9762 <span class=\"lang:default decode:true crayon-inline\">std::sort()<\/span>\u00a0 \u590d\u6742\u5ea6\u4f1a\u591a\u4e2a \\(log\\)\uff08\u867d\u7136\u5bf9\u4e8e\u6570\u636e\u6c34\u7684\u4e5f\u80fd\u8fc7\uff09\uff0c\u4f46\u662f\u8fd0\u7528<strong>\u5f52\u5e76\u6392\u5e8f<\/strong>\u7684\u601d\u60f3\u5c31\u53ef\u4ee5\u8fbe\u5230 \\(O(nlogn)\\) \u7684\u590d\u6742\u5ea6\u3002<\/p>\n<p>\u9996\u5148\u5728\u5916\u9762\u628a\u5143\u7d20\u6309\u7167\u659c\u7387 \\(k\\) \u6392\u5e8f\uff0c\u7136\u540e\u5f00\u59cb CDQ\u5206\u6cbb\u3002<\/p>\n<p>\u5bf9\u4e8e\u533a\u95f4 \\([l, r]\\) \uff0c\u628a\u5176\u4e2d\u5143\u7d20\u7684\u7f16\u53f7\u6309\u7167\u4e0e \\(mid\\) \u7684\u5927\u5c0f\u8fdb\u884c\u5206\u7c7b\uff0c\\(\\leq mid\\) \u7684\u5206\u5230\u5de6\u8fb9\uff0c\\(&gt;mid\\) \u7684\u5206\u5230\u53f3\u8fb9\uff0c\u56e0\u4e3a\u8981\u7528 \\([l, mid]\\) \u4e2d\u7684\u70b9\u66f4\u65b0 \\((mid, r]\\)\uff0c\u6240\u4ee5\u8981\u5148\u628a\u8fd9\u4e9b\u70b9\u627e\u51fa\u6765\uff08\u4e5f\u53ef\u4ee5\u7406\u89e3\u6210\u6309\u7f16\u53f7<strong>\u5f52\u5e76\u6392\u5e8f<\/strong>\u7684\u4e00\u90e8\u5206\uff0c\u503c\u5f97\u6ce8\u610f\u7684\u662f\u8fd9\u6837\u7684\u5206\u6cd5<strong>\u4e0d\u4f1a<\/strong>\u7834\u574f<strong>\u659c\u7387<span style=\"text-decoration: underline;\">\u5206\u522b<\/span><\/strong>\u5728\u5de6\u533a\u95f4\u548c\u53f3\u533a\u95f4\u7684<strong>\u5355\u8c03\u6027<\/strong>\uff0c\u5373\u8fd9\u4e00\u64cd\u4f5c\uff08<strong>\u53ea\u5305\u62ec<\/strong>\u6309\u7167 \\(mid\\) \u5206\u7c7b\uff09\u5b8c\u6210\u540e\u5de6\u53f3\u4e24\u4e2a\u533a\u95f4\u4e2d\u7684\u659c\u7387\u4ecd\u7136\u662f\u5206\u522b\u5355\u8c03\u7684\uff09\u3002<\/p>\n<p>\u63a5\u7740\u9012\u5f52\u8fdb \\([l, mid]\\) \uff0c\u4fdd\u8bc1\u5de6\u533a\u95f4\u5df2\u7ecf\u88ab\u5904\u7406\u8fc7\u4e86\uff0c\u624d\u80fd\u66f4\u65b0\u53f3\u533a\u95f4\u7684\u5143\u7d20\u3002<\/p>\n<p>\u73b0\u5728\u5de6\u533a\u95f4\u7684<strong>\u70b9<\/strong>\u548c<strong>\u4fe1\u606f<\/strong>\u90fd\u88ab\u5904\u7406\u597d\u4e86\uff0c\u5e76\u4e14 <strong>\\(x\\) \u662f\u5355\u8c03\u7684<\/strong>\uff08\u5df2\u7ecf\u88ab\u5904\u7406\u597d\u4e86\uff0c\u8be6\u89c1\u540e\u8ff0\uff09\uff0c\u52a0\u4e0a\u53f3\u533a\u95f4\u7684\u5143\u7d20\u7684<strong>\u659c\u7387 \\(k\\) \u662f\u5355\u8c03<\/strong>\u7684\uff08\u8fd8\u6ca1\u6709\u88ab\u5904\u7406\u8fc7\uff09\uff0c\u6240\u4ee5\u5c31\u53ef\u4ee5\u628a\u5de6\u533a\u95f4\u7684\u70b9\u52a0\u5165\u5355\u8c03\u961f\u5217\uff0c\u7136\u540e\u53bb\u66f4\u65b0\u53f3\u533a\u95f4\u7684\u5143\u7d20\u3002<\/p>\n<p>\u4f46\u662f\u73b0\u5728 \\((mid, r]\\) \u4e2d\u7684\u5143\u7d20\u53ea\u6709\u6765\u81ea \\([l, mid]\\) \u7684\u8d21\u732e\uff0c\u53ef\u80fd\u53d6\u4e0d\u5230\u6700\u4f18\u89e3\uff0c\u6240\u4ee5\u4e3a\u4e86\u4fdd\u8bc1<strong>\u6b63\u786e\u6027<\/strong>\u8fd8\u8981\u9012\u5f52\u8fdb \\((mid, r]\\) \u7ee7\u7eed\u5904\u7406\u53f3\u533a\u95f4\u3002<\/p>\n<p>\u6700\u540e\u4e0d\u8981\u5fd8\u4e86\uff0c\u8981\u5229\u7528<strong>\u5f52\u5e76\u6392\u5e8f<\/strong>\u5c06 \\([l ,r]\\) \u4e2d \u70b9\u7684 <strong>\\(x\\) \u53d8\u4e3a\u5355\u8c03<\/strong>\u7684\uff0c\u8fd9\u6837\u624d\u80fd\u4fdd\u8bc1\u524d\u9762\u64cd\u4f5c\u7684\u6b63\u786e\u6027\u3002\uff08\u53ef\u4ee5\u7406\u89e3\u4e3a\u9012\u5f52\u8fdb\u4e00\u4e2a\u533a\u95f4\u540e\uff0c\u8fd9\u4e2a\u533a\u95f4\u5185\u70b9\u7684 \\(x\\) \u5c31\u4f1a\u88ab\u5904\u7406\u6210\u5355\u8c03\u7684\uff0c\u53ef\u4ee5\u8fdb\u884c\u540e\u7eed\u7684\u64cd\u4f5c\uff09<\/p>\n<p>\u8fd9\u5c31\u662f CDQ\u5206\u6cbb \u7684\u5927\u81f4\u8fc7\u7a0b\u3002<\/p>\n<p>\u5176\u5b9e\u4e0a\u9762\u8bf4\u4e86\u8fd9\u4e48\u591a\uff0c\u5c31\u662f\u8981\u8ba9\u533a\u95f4 \\([l, r]\\) \u6ee1\u8db3\u5982\u4e0b\u7684\u5173\u7cfb\uff1a<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1010\" src=\"https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/cdq.png\" alt=\"\" width=\"529\" height=\"290\" srcset=\"https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/cdq.png 529w, https:\/\/0self.mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/cdq-300x164.png 300w\" sizes=\"auto, (max-width: 529px) 100vw, 529px\" \/><\/p>\n<p>\u53ef\u4ee5\u7ed3\u5408\u7740\u56fe\u601d\u8003\u6bcf\u4e00\u4e2a\u64cd\u4f5c\u5206\u522b\u6709\u4ec0\u4e48\u610f\u4e49\u3002<\/p>\n<p>&nbsp;<\/p>\n<p>\u8fd9\u6837\uff0c\u659c\u7387\u4f18\u5316\u7684\u57fa\u7840\u77e5\u8bc6\u5c31\u5927\u6982\u5230\u8fd9\u91cc\u4e86\u3002<del>\uff08\u9ad8\u7ea7\u7684\u6211\u4e5f\u4e0d\u4f1a\uff09<\/del><\/p>\n<p>\u63a5\u4e0b\u6765\u662f\u4e00\u4e9b\u9898\u76ee\uff08\u5206\u6790\u91cc\u4ecd\u7136\u4f1a\u6709\u4e00\u4e9b\u672c\u7bc7\u6587\u7ae0\u7684\u201c\u539f\u7a3f\u201d\uff0c\u6211\u4e5f\u4e0d\u6253\u7b97\u6539\u4e86\uff09<\/p>\n<p>1\uff0c<a href=\"https:\/\/0self.mnihyc.com\/blog\/archives\/897\">[APIO2014]sequence<\/a> \u3001 <a href=\"https:\/\/0self.mnihyc.com\/blog\/archives\/806\">[USACO2008 Mar]\u571f\u5730\u8d2d\u4e70<\/a><\/p>\n<p>2\uff0c<a href=\"https:\/\/0self.mnihyc.com\/blog\/archives\/913\">[SDOI2012]\u4efb\u52a1\u5b89\u6392<\/a><\/p>\n<p>3\uff0c<a href=\"https:\/\/0self.mnihyc.com\/blog\/archives\/930\">[CEOI2017]Building Bridges<\/a> \u3001\u00a0<a href=\"https:\/\/0self.mnihyc.com\/blog\/archives\/947\">[2018\u7701\u961f\u96c6\u8bad]\u5e8f\u5217<\/a><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316 \u6700\u8fd1\uff08\u4e24\u4e2a\u6708\u524d\uff09\u5b66\u4e60\u4e86\u659c\u7387\u4f18\u5316 \u2014\u2014 \u4e00\u79cd\u4f18\u5316 1D1D \u52a8\u6001\u89c4\u5212\u8f6c\u79fb\u65b9\u7a0b\u7684\u9ad8\u6548\u65b9\u6cd5 &hellip; <a href=\"https:\/\/0self.mnihyc.com\/blog\/archives\/993\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[67,43],"tags":[],"class_list":["post-993","post","type-post","status-publish","format-standard","hentry","category-topic","category-slopedp"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.1.1 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316 - mnihyc&#039;s Blog<\/title>\n<meta name=\"description\" content=\"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316 \u6700\u8fd1\uff08\u4e24\u4e2a\u6708\u524d\uff09\u5b66\u4e60\u4e86\u659c\u7387\u4f18\u5316 \u2014\u2014 \u4e00\u79cd\u4f18\u5316 1D1D \u52a8\u6001\u89c4\u5212\u8f6c\u79fb\u65b9\u7a0b\u7684\u9ad8\u6548\u65b9\u6cd5\uff0c\u5728\u8f83\u9ad8\u96be\u5ea6\u7684\u6bd4\u8d5b\u4e2d\u662f\u4e00\u79cd\u5341\u5206\u5e38\u89c1\u7684 DP \u4f18\u5316\u624b\u6bb5\u3002\u9274\u4e8e\u6211\u4e4b\u524d\uff08\u4e00\u5e74\u524d\uff09\u4e5f\u7a0d\u5fae\u63a5\u89e6\u8fc7\u4e00\u70b9\u76f8\u5173\u65b9\u9762\u7684\u77e5\u8bc6\uff0c\u4f46\u662f\u5b8c\u5168\u6ca1\u6709\u641e\u61c2\uff08\u592a\u83dc\u4e86\uff09\uff0c\u6700\u8fd1\uff08\u4e24\u4e2a\u6708\u524d\uff09\u518d\u914d\u5408 orzCJK\u5b66\u957f\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/mnihyc.com\/blog\/archives\/993\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316 - mnihyc&#039;s Blog\" \/>\n<meta property=\"og:description\" content=\"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316 \u6700\u8fd1\uff08\u4e24\u4e2a\u6708\u524d\uff09\u5b66\u4e60\u4e86\u659c\u7387\u4f18\u5316 \u2014\u2014 \u4e00\u79cd\u4f18\u5316 1D1D \u52a8\u6001\u89c4\u5212\u8f6c\u79fb\u65b9\u7a0b\u7684\u9ad8\u6548\u65b9\u6cd5\uff0c\u5728\u8f83\u9ad8\u96be\u5ea6\u7684\u6bd4\u8d5b\u4e2d\u662f\u4e00\u79cd\u5341\u5206\u5e38\u89c1\u7684 DP \u4f18\u5316\u624b\u6bb5\u3002\u9274\u4e8e\u6211\u4e4b\u524d\uff08\u4e00\u5e74\u524d\uff09\u4e5f\u7a0d\u5fae\u63a5\u89e6\u8fc7\u4e00\u70b9\u76f8\u5173\u65b9\u9762\u7684\u77e5\u8bc6\uff0c\u4f46\u662f\u5b8c\u5168\u6ca1\u6709\u641e\u61c2\uff08\u592a\u83dc\u4e86\uff09\uff0c\u6700\u8fd1\uff08\u4e24\u4e2a\u6708\u524d\uff09\u518d\u914d\u5408 orzCJK\u5b66\u957f\" \/>\n<meta property=\"og:url\" content=\"https:\/\/mnihyc.com\/blog\/archives\/993\" \/>\n<meta property=\"og:site_name\" content=\"mnihyc&#039;s Blog\" \/>\n<meta property=\"article:published_time\" content=\"2019-02-21T14:13:47+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-02-08T19:01:13+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope.png\" \/>\n<meta name=\"author\" content=\"mnihyc\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@mnihyc\" \/>\n<meta name=\"twitter:site\" content=\"@mnihyc\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"mnihyc\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/993#article\",\"isPartOf\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/993\"},\"author\":{\"name\":\"mnihyc\",\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\"},\"headline\":\"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316\",\"datePublished\":\"2019-02-21T14:13:47+00:00\",\"dateModified\":\"2020-02-08T19:01:13+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/993\"},\"wordCount\":243,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\"},\"image\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/993#primaryimage\"},\"thumbnailUrl\":\"https:\/\/mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope.png\",\"articleSection\":[\"\u4e13\u9898\",\"\u659c\u7387\u4f18\u5316\"],\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/mnihyc.com\/blog\/archives\/993#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/993\",\"url\":\"https:\/\/mnihyc.com\/blog\/archives\/993\",\"name\":\"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316 - mnihyc&#039;s Blog\",\"isPartOf\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/993#primaryimage\"},\"image\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/993#primaryimage\"},\"thumbnailUrl\":\"https:\/\/mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope.png\",\"datePublished\":\"2019-02-21T14:13:47+00:00\",\"dateModified\":\"2020-02-08T19:01:13+00:00\",\"description\":\"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316 \u6700\u8fd1\uff08\u4e24\u4e2a\u6708\u524d\uff09\u5b66\u4e60\u4e86\u659c\u7387\u4f18\u5316 \u2014\u2014 \u4e00\u79cd\u4f18\u5316 1D1D \u52a8\u6001\u89c4\u5212\u8f6c\u79fb\u65b9\u7a0b\u7684\u9ad8\u6548\u65b9\u6cd5\uff0c\u5728\u8f83\u9ad8\u96be\u5ea6\u7684\u6bd4\u8d5b\u4e2d\u662f\u4e00\u79cd\u5341\u5206\u5e38\u89c1\u7684 DP \u4f18\u5316\u624b\u6bb5\u3002\u9274\u4e8e\u6211\u4e4b\u524d\uff08\u4e00\u5e74\u524d\uff09\u4e5f\u7a0d\u5fae\u63a5\u89e6\u8fc7\u4e00\u70b9\u76f8\u5173\u65b9\u9762\u7684\u77e5\u8bc6\uff0c\u4f46\u662f\u5b8c\u5168\u6ca1\u6709\u641e\u61c2\uff08\u592a\u83dc\u4e86\uff09\uff0c\u6700\u8fd1\uff08\u4e24\u4e2a\u6708\u524d\uff09\u518d\u914d\u5408 orzCJK\u5b66\u957f\",\"breadcrumb\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/993#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/mnihyc.com\/blog\/archives\/993\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/993#primaryimage\",\"url\":\"https:\/\/mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope.png\",\"contentUrl\":\"https:\/\/mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/mnihyc.com\/blog\/archives\/993#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/mnihyc.com\/blog\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/mnihyc.com\/blog\/#website\",\"url\":\"https:\/\/mnihyc.com\/blog\/\",\"name\":\"mnihyc&#039;s Blog\",\"description\":\"Welcome!\",\"publisher\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/mnihyc.com\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"zh-Hans\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\",\"name\":\"mnihyc\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g\",\"caption\":\"mnihyc\"},\"logo\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/image\/\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316 - mnihyc&#039;s Blog","description":"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316 \u6700\u8fd1\uff08\u4e24\u4e2a\u6708\u524d\uff09\u5b66\u4e60\u4e86\u659c\u7387\u4f18\u5316 \u2014\u2014 \u4e00\u79cd\u4f18\u5316 1D1D \u52a8\u6001\u89c4\u5212\u8f6c\u79fb\u65b9\u7a0b\u7684\u9ad8\u6548\u65b9\u6cd5\uff0c\u5728\u8f83\u9ad8\u96be\u5ea6\u7684\u6bd4\u8d5b\u4e2d\u662f\u4e00\u79cd\u5341\u5206\u5e38\u89c1\u7684 DP \u4f18\u5316\u624b\u6bb5\u3002\u9274\u4e8e\u6211\u4e4b\u524d\uff08\u4e00\u5e74\u524d\uff09\u4e5f\u7a0d\u5fae\u63a5\u89e6\u8fc7\u4e00\u70b9\u76f8\u5173\u65b9\u9762\u7684\u77e5\u8bc6\uff0c\u4f46\u662f\u5b8c\u5168\u6ca1\u6709\u641e\u61c2\uff08\u592a\u83dc\u4e86\uff09\uff0c\u6700\u8fd1\uff08\u4e24\u4e2a\u6708\u524d\uff09\u518d\u914d\u5408 orzCJK\u5b66\u957f","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/mnihyc.com\/blog\/archives\/993","og_locale":"zh_CN","og_type":"article","og_title":"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316 - mnihyc&#039;s Blog","og_description":"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316 \u6700\u8fd1\uff08\u4e24\u4e2a\u6708\u524d\uff09\u5b66\u4e60\u4e86\u659c\u7387\u4f18\u5316 \u2014\u2014 \u4e00\u79cd\u4f18\u5316 1D1D \u52a8\u6001\u89c4\u5212\u8f6c\u79fb\u65b9\u7a0b\u7684\u9ad8\u6548\u65b9\u6cd5\uff0c\u5728\u8f83\u9ad8\u96be\u5ea6\u7684\u6bd4\u8d5b\u4e2d\u662f\u4e00\u79cd\u5341\u5206\u5e38\u89c1\u7684 DP \u4f18\u5316\u624b\u6bb5\u3002\u9274\u4e8e\u6211\u4e4b\u524d\uff08\u4e00\u5e74\u524d\uff09\u4e5f\u7a0d\u5fae\u63a5\u89e6\u8fc7\u4e00\u70b9\u76f8\u5173\u65b9\u9762\u7684\u77e5\u8bc6\uff0c\u4f46\u662f\u5b8c\u5168\u6ca1\u6709\u641e\u61c2\uff08\u592a\u83dc\u4e86\uff09\uff0c\u6700\u8fd1\uff08\u4e24\u4e2a\u6708\u524d\uff09\u518d\u914d\u5408 orzCJK\u5b66\u957f","og_url":"https:\/\/mnihyc.com\/blog\/archives\/993","og_site_name":"mnihyc&#039;s Blog","article_published_time":"2019-02-21T14:13:47+00:00","article_modified_time":"2020-02-08T19:01:13+00:00","og_image":[{"url":"https:\/\/mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope.png","type":"","width":"","height":""}],"author":"mnihyc","twitter_card":"summary_large_image","twitter_creator":"@mnihyc","twitter_site":"@mnihyc","twitter_misc":{"\u4f5c\u8005":"mnihyc","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"1 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/mnihyc.com\/blog\/archives\/993#article","isPartOf":{"@id":"https:\/\/mnihyc.com\/blog\/archives\/993"},"author":{"name":"mnihyc","@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751"},"headline":"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316","datePublished":"2019-02-21T14:13:47+00:00","dateModified":"2020-02-08T19:01:13+00:00","mainEntityOfPage":{"@id":"https:\/\/mnihyc.com\/blog\/archives\/993"},"wordCount":243,"commentCount":0,"publisher":{"@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751"},"image":{"@id":"https:\/\/mnihyc.com\/blog\/archives\/993#primaryimage"},"thumbnailUrl":"https:\/\/mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope.png","articleSection":["\u4e13\u9898","\u659c\u7387\u4f18\u5316"],"inLanguage":"zh-Hans","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/mnihyc.com\/blog\/archives\/993#respond"]}]},{"@type":"WebPage","@id":"https:\/\/mnihyc.com\/blog\/archives\/993","url":"https:\/\/mnihyc.com\/blog\/archives\/993","name":"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316 - mnihyc&#039;s Blog","isPartOf":{"@id":"https:\/\/mnihyc.com\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/mnihyc.com\/blog\/archives\/993#primaryimage"},"image":{"@id":"https:\/\/mnihyc.com\/blog\/archives\/993#primaryimage"},"thumbnailUrl":"https:\/\/mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope.png","datePublished":"2019-02-21T14:13:47+00:00","dateModified":"2020-02-08T19:01:13+00:00","description":"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316 \u6700\u8fd1\uff08\u4e24\u4e2a\u6708\u524d\uff09\u5b66\u4e60\u4e86\u659c\u7387\u4f18\u5316 \u2014\u2014 \u4e00\u79cd\u4f18\u5316 1D1D \u52a8\u6001\u89c4\u5212\u8f6c\u79fb\u65b9\u7a0b\u7684\u9ad8\u6548\u65b9\u6cd5\uff0c\u5728\u8f83\u9ad8\u96be\u5ea6\u7684\u6bd4\u8d5b\u4e2d\u662f\u4e00\u79cd\u5341\u5206\u5e38\u89c1\u7684 DP \u4f18\u5316\u624b\u6bb5\u3002\u9274\u4e8e\u6211\u4e4b\u524d\uff08\u4e00\u5e74\u524d\uff09\u4e5f\u7a0d\u5fae\u63a5\u89e6\u8fc7\u4e00\u70b9\u76f8\u5173\u65b9\u9762\u7684\u77e5\u8bc6\uff0c\u4f46\u662f\u5b8c\u5168\u6ca1\u6709\u641e\u61c2\uff08\u592a\u83dc\u4e86\uff09\uff0c\u6700\u8fd1\uff08\u4e24\u4e2a\u6708\u524d\uff09\u518d\u914d\u5408 orzCJK\u5b66\u957f","breadcrumb":{"@id":"https:\/\/mnihyc.com\/blog\/archives\/993#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/mnihyc.com\/blog\/archives\/993"]}]},{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/mnihyc.com\/blog\/archives\/993#primaryimage","url":"https:\/\/mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope.png","contentUrl":"https:\/\/mnihyc.com\/blog\/wp-content\/uploads\/2019\/02\/slope.png"},{"@type":"BreadcrumbList","@id":"https:\/\/mnihyc.com\/blog\/archives\/993#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/mnihyc.com\/blog"},{"@type":"ListItem","position":2,"name":"\u6d45\u8c08\u659c\u7387\u4f18\u5316\u2014\u2014\u622a\u8ddd\u4f18\u5316"}]},{"@type":"WebSite","@id":"https:\/\/mnihyc.com\/blog\/#website","url":"https:\/\/mnihyc.com\/blog\/","name":"mnihyc&#039;s Blog","description":"Welcome!","publisher":{"@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/mnihyc.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"zh-Hans"},{"@type":["Person","Organization"],"@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751","name":"mnihyc","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g","caption":"mnihyc"},"logo":{"@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/image\/"}}]}},"_links":{"self":[{"href":"https:\/\/0self.mnihyc.com\/blog\/wp-json\/wp\/v2\/posts\/993","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/0self.mnihyc.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/0self.mnihyc.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/0self.mnihyc.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/0self.mnihyc.com\/blog\/wp-json\/wp\/v2\/comments?post=993"}],"version-history":[{"count":0,"href":"https:\/\/0self.mnihyc.com\/blog\/wp-json\/wp\/v2\/posts\/993\/revisions"}],"wp:attachment":[{"href":"https:\/\/0self.mnihyc.com\/blog\/wp-json\/wp\/v2\/media?parent=993"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/0self.mnihyc.com\/blog\/wp-json\/wp\/v2\/categories?post=993"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/0self.mnihyc.com\/blog\/wp-json\/wp\/v2\/tags?post=993"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}