{"id":182,"date":"2011-08-18T12:25:08","date_gmt":"2011-08-18T04:25:08","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=182"},"modified":"2020-06-04T12:25:41","modified_gmt":"2020-06-04T04:25:41","slug":"poj-1163-the-triangle","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=182","title":{"rendered":"poj 1163 The Triangle"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>\/*\n\u5165\u95e8\u7ea7dp\ndp\u5fc5\u505a\n*\/\n#define LOCAL\n#include&lt;iostream>\n#include&lt;cstdio>\n#include&lt;cmath>\n#include&lt;cstring>\n#include&lt;cstdlib>\n#include&lt;iomanip>\n#include&lt;string>\n#include&lt;algorithm>\n#include&lt;ctime>\n#include&lt;stack>\n#include&lt;queue>\n#include&lt;vector>\n#define N 105\nusing namespace std;\nint dp&#91;N]&#91;N],a&#91;N]&#91;N];\nint main()\n{\n#ifdef LOCAL\n       freopen(\"input.txt\",\"r\",stdin);\n       freopen(\"output.txt\",\"w\",stdout);\n#endif\n \n\tint i,j,len,max;\n\tmemset(dp,0,sizeof(dp));\n\tmemset(a,0,sizeof(a));\n\tcin>>len;\n\tfor(i=1;i&lt;=len;i++)\n\t\tfor(j=1;j&lt;=i;j++)\n\t\t\tcin>>a&#91;i]&#91;j];\n\tfor(i=1;i&lt;=len;i++)\n\t{\n\t\tfor(j=1;j&lt;=i;j++)\n\t\t{\n\t\t\tif(j==1){dp&#91;i]&#91;j]=dp&#91;i-1]&#91;j]+a&#91;i]&#91;j];}\n\t\t\telse if(i==j){dp&#91;i]&#91;j]=dp&#91;i-1]&#91;j-1]+a&#91;i]&#91;j];}\n\t\t\telse dp&#91;i]&#91;j]=a&#91;i]&#91;j]+(dp&#91;i-1]&#91;j]>dp&#91;i-1]&#91;j-1]?dp&#91;i-1]&#91;j]:dp&#91;i-1]&#91;j-1]);\n\t\t}\n\t}\n\tmax=dp&#91;len]&#91;1];\n\tfor(i=2;i&lt;=len;i++)\n\t\tif(max&lt;dp&#91;len]&#91;i])\n\t\t\t max=dp&#91;len]&#91;i];\n\tcout&lt;&lt;max&lt;&lt;endl;\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-182","post","type-post","status-publish","format-standard","hentry","category-06-01-acm"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/182","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=182"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/182\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=182"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=182"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=182"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}