{"id":305,"date":"2020-03-19T18:40:00","date_gmt":"2020-03-19T10:40:00","guid":{"rendered":"http:\/\/ff.mhrooz.xyz\/?p=305"},"modified":"2020-03-19T18:40:00","modified_gmt":"2020-03-19T10:40:00","slug":"lightoj-1422_qu_jian_dp","status":"publish","type":"post","link":"https:\/\/blog.mhrooz.xyz\/index.php\/2020\/03\/19\/lightoj-1422_qu_jian_dp\/","title":{"rendered":"LightOJ-1422 \u533a\u95f4dp"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">\u9898\u610f<\/h2>\n\n\n\n<p> \u5c0f\u7070\u7070\u53c2\u52a0\u5723\u8bde\u8282\u7684\u4e00\u4e9b\u6d3e\u5bf9\uff0c\u5e76\u4e14\u9700\u8981\u7a7f\u4e0a\u5bf9\u5e94\u6d3e\u5bf9\u7684\u8863\u670d\uff0c\u6240\u4ee5\u4ed6\u9700\u8981\u591a\u6b21\u6362\u8863\u670d\uff0c\u4e3a\u4e86\u65b9\u4fbf\uff0c\u4ed6\u53ef\u4ee5\u9009\u62e9\u8131\u6389\u4e00\u4e9b\u8863\u670d\u6216\u8005\u7a7f\u4e0a\u65b0\u8863\u670d\uff0c\u6bd4\u5982\u8bf4\uff0c\u4ed6\u7a7f\u7740\u8d85\u4eba\u7684\u8863\u670d\uff0c\u5916\u9762\u53c8\u7a7f\u7740\u6b7b\u4f8d\u7684\u8863\u670d\uff0c\u5f53\u4ed6\u8981\u53c2\u52a0\u8d85\u4eba\u670d\u88c5\u6d3e\u5bf9\u65f6\uff0c\u4ed6\u53ef\u4ee5\u9009\u62e9\u8131\u6389\u6b7b\u4f8d\u7684\u8863\u670d\uff08\u56e0\u4e3a\u6b7b\u4f8d\u8863\u670d\u7684\u91cc\u9762\u6709\u8d85\u4eba\u7684\u8863\u670d\uff09\uff0c\u6216\u8005\u4ed6\u53ef\u4ee5\u5728\u7a7f\u4e00\u4ef6\u8d85\u4eba\u7684\u8863\u670d\uff0c\u5c0f\u7070\u7070\u662f\u4e2a\u7231\u5e72\u51c0\u7684\u4eba\uff0c\u5f53\u4ed6\u8131\u4e0b\u6b7b\u4f8d\u7684\u8863\u670d\u540e\uff0c\u5982\u679c\u9700\u8981\u518d\u7a7f\u6b7b\u4f8d\u7684\u8863\u670d\uff0c\u4ed6\u4f1a\u9009\u62e9\u518d\u7a7f\u4e00\u4ef6\u65b0\u7684\u3002\uff08\u5982\u679c\u4ed6\u5148\u7a7fA\u8863\u670d\uff0c\u53c8\u7a7f\u4e0aB\u8863\u670d\uff0c\u518d\u7a7f\u4e00\u4ef6C\u8863\u670d\uff0c\u5982\u679c\u4ed6\u60f3\u8ba9\u6700\u5916\u9762\u7684\u8863\u670d\u662fA\uff0c\u4ed6\u53ef\u4ee5\u9009\u62e9\u76f4\u63a5\u7a7f\u4e00\u4ef6A\uff0c\u6216\u8005\u5148\u628aC\u8131\u6389\uff0c\u518d\u628aB\u8131\u6389\uff09\u3002 <\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u9898\u89e3<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"true\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/*\nO(n3)\n\u533a\u95f4dp\ndp\u8d77\u70b9\u4e3a\u8d77\u70b9\u548c\u7ec8\u70b9\u76f8\u540c\u7684\u4e3a1\n\u7136\u540e\u5f00\u59cb\u679a\u4e3e\u4e2d\u95f4\u70b9\uff0c\ndp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);\n\u5982\u679c\u8d77\u70b9\u548c\u7ec8\u70b9\u7684\u503c\u4e00\u6837\u5c31\u5728\u679a\u4e3e\u524d\u8bbe\u7f6e\ndp[i][j]=dp[i][j-1]\n*\/\n#include &lt;map>\n#include &lt;set>\n#include &lt;cmath>\n#include &lt;queue>\n#include &lt;stack>\n#include &lt;string>\n#include &lt;cstdio>\n#include &lt;vector>\n#include &lt;climits>\n#include &lt;cstring>\n#include &lt;cstdlib>\n#include &lt;iostream>\n#include &lt;algorithm>\nusing namespace std;\ntypedef long long ll;\nconst int maxn = 240;\nint n;\nint num[maxn], dp[maxn][maxn];\nint main()\n{\n    ios::sync_with_stdio(0);\n    \/\/ freopen(\"a.in\", \"r\", stdin);\n    int __t, dd = 1;\n    cin >> __t;\n    while (__t--)\n    {\n        cin >> n;\n        for (int i = 1; i &lt;= n; i++)\n            cin >> num[i];\n        for (int i = 1; i &lt;= n; i++)\n            for (int j = 1; j &lt;= n; j++)\n                dp[i][j] = 0x3f3f3f3f;\n        for (int i = 1; i &lt;= n; i++)\n            dp[i][i] = 1;\n\n        for (int len = 1; len &lt; n; len++)\n        {\n            for (int i = 1; i + len &lt;= n; i++)\n            {\n                int j = i + len;\n                if (num[i] == num[j])\n                    dp[i][j] = dp[i][j - 1];\n                for (int k = i; k &lt; i + len; k++)\n                {\n                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);\n                }\n            }\n        }\n        cout &lt;&lt; \"Case \" &lt;&lt; dd++ &lt;&lt; \": \" &lt;&lt; dp[1][n] &lt;&lt; endl;\n    }\n\n    return 0;\n}<\/pre>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u610f \u5c0f\u7070\u7070\u53c2\u52a0\u5723\u8bde\u8282\u7684\u4e00\u4e9b\u6d3e\u5bf9\uff0c\u5e76\u4e14\u9700\u8981\u7a7f\u4e0a\u5bf9\u5e94\u6d3e\u5bf9\u7684\u8863\u670d\uff0c\u6240\u4ee5\u4ed6\u9700\u8981\u591a\u6b21\u6362\u8863\u670d\uff0c\u4e3a\u4e86\u65b9\u4fbf\uff0c\u4ed6\u53ef\u4ee5\u9009\u62e9\u8131\u6389\u4e00<a class=\"more-link\" href=\"https:\/\/blog.mhrooz.xyz\/index.php\/2020\/03\/19\/lightoj-1422_qu_jian_dp\/\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">&#8220;LightOJ-1422 \u533a\u95f4dp&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/blog.mhrooz.xyz\/index.php\/wp-json\/wp\/v2\/posts\/305"}],"collection":[{"href":"https:\/\/blog.mhrooz.xyz\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.mhrooz.xyz\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.mhrooz.xyz\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.mhrooz.xyz\/index.php\/wp-json\/wp\/v2\/comments?post=305"}],"version-history":[{"count":1,"href":"https:\/\/blog.mhrooz.xyz\/index.php\/wp-json\/wp\/v2\/posts\/305\/revisions"}],"predecessor-version":[{"id":306,"href":"https:\/\/blog.mhrooz.xyz\/index.php\/wp-json\/wp\/v2\/posts\/305\/revisions\/306"}],"wp:attachment":[{"href":"https:\/\/blog.mhrooz.xyz\/index.php\/wp-json\/wp\/v2\/media?parent=305"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.mhrooz.xyz\/index.php\/wp-json\/wp\/v2\/categories?post=305"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.mhrooz.xyz\/index.php\/wp-json\/wp\/v2\/tags?post=305"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}