{"id":168,"date":"2011-08-14T12:20:16","date_gmt":"2011-08-14T04:20:16","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=168"},"modified":"2020-06-04T12:20:49","modified_gmt":"2020-06-04T04:20:49","slug":"zoj-1733-common-subsequence","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=168","title":{"rendered":"zoj 1733 Common Subsequence"},"content":{"rendered":"\n
\/*\n\u52a8\u6001\u89c4\u5212\u9898\n\u4e5f\u8bb8\u662f\u521a\u521a\u63a5\u89e6\u52a8\u6001\u89c4\u5212\u7684\u7f18\u6545\n\u53d1\u73b0\u4ed6\u771f\u7684\u662f\u5947\u5999\u65e0\u7a77\n\u8bb8\u591a\u770b\u4f3c\u65e0\u6cd5\u53ef\u89e3\u7684\u95ee\u9898\u7528\u5b83\u5c31\u53ef\u4ee5\u5f88\u8f7b\u6613\u5730\u89e3\u51b3\n\u6b64\u9898\u662f\u6c42\u6700\u957f\u516c\u5171\u5b50\u4e32\u7684\u95ee\u9898\n\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\ndp[i][j]=dp[i-1][j-1]+1; (str1[i]==str2[j])\ndp[i][j]=MAX{dp[i-1][j],dp[i][j-1]}; (str1[i]!=str2[j])\n\u6700\u540e\u8f93\u51fadp[i][j]\u5373\u53ef\n\u5bf9\u4e8e\u5b57\u7b26\u4e32\nstr1=\"X1X2...Xi...Xm\";\nstr2=\"Y1Y2...Yj...Yn\";\n\u82e5Xi==Yj\n\u5219str1\uff0cstr2\u7684\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\u957f\u4e00\u5b9a\u7b49\u4e8e\"X1X2...Xi-1\" ,\"Y1Y2...Yj-1\"\n\u7684\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\u957f\u5ea6+1\n\u540c\u7406\u82e5Xi\uff01=Xj\uff0c\u5219str1\uff0cstr2\u7684\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\u957f\n\u4e00\u5b9a\u7b49\u4e8e\"X1X2...Xi-1\"\u548c\"Y1Y2...Yj\" ,\"Y1Y2...Yj-1\"\u548c\"X1X2...Xi\"\u4e2d\u8f83\u957f\u7684\u516c\u5171\u5b50\u5e8f\u5217\u957f\u5ea6\n*\/\n#define LOCAL\n#include<iostream>\n#include<cstdio>\n#include<cmath>\n#include<cstring>\n#include<cstdlib>\n#include<iomanip>\n#include<string>\n#include<algorithm>\n#include<ctime>\n#include<stack>\n#include<queue>\n#include<vector>\n#define N 1005\nusing namespace std;\nint dp[N][N];\nint main()\n{\n#ifdef LOCAL\n       freopen(\"input.txt\",\"r\",stdin);\n       freopen(\"output.txt\",\"w\",stdout);\n#endif\n \n\tstring str1,str2;\n\tint strlen1,strlen2,i,j;\n\twhile(cin>>str1>>str2)\n\t{\n\t\tmemset(dp,0,sizeof(dp));\n\t\tstrlen1=str1.size();strlen2=str2.size();\n\t\tfor(i=1;i<=strlen1;i++)\n\t\t{\n\t\t\tfor(j=1;j<=strlen2;j++)\n\t\t\t{\n\t\t\t\tif(str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1]+1;\n\t\t\t\telse dp[i][j]=(dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1]);\n\t\t\t}\n\t    }\n\t\tcout<<dp[strlen1][strlen2]<<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-168","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\/168","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=168"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/168\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=168"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=168"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=168"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}