{"id":170,"date":"2011-08-15T12:21:05","date_gmt":"2011-08-15T04:21:05","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=170"},"modified":"2020-06-04T12:21:35","modified_gmt":"2020-06-04T04:21:35","slug":"zoj-1642-match-for-bonus","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=170","title":{"rendered":"zoj 1642 Match for Bonus"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>\/*\n\u6ce8\u610f\u6570\u7ec4\u957f\u5ea6\n\u5c0f\u7684\u8bdd\u4f1aSF\n\u5927\u7684\u8bdd\u4f1aMLE\n\u63d0\u4ea4\u4e86\u56db\u6b21\n2005\u6b63\u597d\n\u7ecf\u5178dp\u9898\n\u4e0e\u6700\u957f\u5b50\u4e32\u4e0d\u540c\u7684\u662f\u76f8\u7b49\u60c5\u51b5\u4e0b\u4e0d\u518d\u52a01\n\u52a0\u7684\u662f\u76f8\u5e94\u5b57\u7b26\u7684\u6743\u503c\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 2005\nusing namespace std;\nint dp&#91;N]&#91;N],nchar;\nclass CH_VALUE\n{public:char ch;int value;};\nCH_VALUE ch_value&#91;N];\nint get_value(char ch)\n{\n\tint i;\n\tfor(i=0;i&lt;nchar;i++)\n\t{if(ch==ch_value&#91;i].ch) return ch_value&#91;i].value;}\n}\nint main()\n{\n#ifdef LOCAL\n       freopen(\"input.txt\",\"r\",stdin);\n       freopen(\"output.txt\",\"w\",stdout);\n#endif\n\tstring str1,str2;\n\tint strlen1,strlen2,i,j;\n\twhile(cin>>nchar)\n\t{\n\t\tfor(i=0;i&lt;nchar;i++)\n\t\t\tcin>>ch_value&#91;i].ch>>ch_value&#91;i].value;\n\t\tcin>>str1>>str2;\n\t\tstrlen1=str1.size();strlen2=str2.size();\n\t\tmemset(dp,0,sizeof(dp));\n\t\tfor(i=1;i&lt;=strlen1;i++)\n\t\t{\n\t\t\tfor(j=1;j&lt;=strlen2;j++)\n\t\t\t{\n\t\t\t\tif(str1&#91;i-1]==str2&#91;j-1]){dp&#91;i]&#91;j]=dp&#91;i-1]&#91;j-1]+get_value(str1&#91;i-1]);}\n\t\t\t\telse{dp&#91;i]&#91;j]=(dp&#91;i-1]&#91;j]>dp&#91;i]&#91;j-1]?dp&#91;i-1]&#91;j]:dp&#91;i]&#91;j-1]);}\n\t\t\t}\n\t\t}\n\t\tcout&lt;&lt;dp&#91;strlen1]&#91;strlen2]&lt;&lt;endl;\n\t}\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-170","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\/170","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=170"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/170\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=170"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=170"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=170"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}