{"id":1176,"date":"2015-07-16T07:38:51","date_gmt":"2015-07-15T23:38:51","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1176"},"modified":"2015-07-16T07:38:51","modified_gmt":"2015-07-15T23:38:51","slug":"poj-1390-blocks","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/poj-1390-blocks\/","title":{"rendered":"POJ 1390. Blocks"},"content":{"rendered":"<p><!--more--><br \/>\n&#8230;<br \/>\nhttp:\/\/poj.org\/problem?id=1390<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;iostream&gt;\r\n#include &lt;cstdio&gt;\r\nusing namespace std;\r\nconst int N = 200, K = 200;\r\n\r\nint d&#x5B;N]&#x5B;N]&#x5B;K];\r\nint color&#x5B;N], len&#x5B;N];\r\nint n;\r\n\r\nint sqr(int x){\r\n    return x*x;\r\n}\r\n\r\nint f(int l, int r, int k){\r\n    if (l&gt;r) return 0;\r\n\r\n    if (d&#x5B;l]&#x5B;r]&#x5B;k]==0){\r\n        if (l==r) d&#x5B;l]&#x5B;r]&#x5B;k] = sqr(len&#x5B;l]+k);\r\n        else{\r\n            d&#x5B;l]&#x5B;r]&#x5B;k] = f(l, r-1, 0) + sqr(len&#x5B;r]+k);\r\n            for (int p=l;p&lt;r;p++){\r\n                if (color&#x5B;p]==color&#x5B;r])\r\n                    d&#x5B;l]&#x5B;r]&#x5B;k] = max(d&#x5B;l]&#x5B;r]&#x5B;k], f(l, p, len&#x5B;r]+k)  + f(p+1, r-1, 0));\r\n            }\r\n        }\r\n    }\r\n    return d&#x5B;l]&#x5B;r]&#x5B;k];\r\n}\r\n\r\nvoid init(){\r\n    int nn, tt, t;cin &gt;&gt; nn;\r\n\r\n    n = 0;\r\n    scanf(&quot;%d&quot;, &amp;t);\r\n    color&#x5B;n] = t; len&#x5B;n] = 1;\r\n\r\n    for (int i=1;i&lt;nn;i++){\r\n        scanf(&quot;%d&quot;, &amp;tt);\r\n        if (tt==t) len&#x5B;n]++;\r\n        else color&#x5B;++n] = tt, t = tt, len&#x5B;n] = 1;\r\n    }\r\n    n++;\r\n\r\n}\r\nint main(){\r\n    int T; cin &gt;&gt; T;\r\n    for (int i=1;i&lt;=T;i++){\r\n        init(); memset(d, 0, sizeof(d));\r\n        printf(&quot;Case %d: %d\\n&quot;, i, f(0, n-1, 0));\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_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","enabled":false}}},"categories":[19],"tags":[],"class_list":["post-1176","post","type-post","status-publish","format-standard","hentry","category-poj"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-iY","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1176","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=1176"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1176\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1176"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1176"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1176"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}