{"id":243,"date":"2020-04-13T23:51:37","date_gmt":"2020-04-13T15:51:37","guid":{"rendered":"http:\/\/47.103.223.234:100\/?p=243"},"modified":"2020-04-14T22:00:10","modified_gmt":"2020-04-14T14:00:10","slug":"%e7%bb%8f%e5%85%b8dp%e4%be%8b%e9%a2%98","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/04\/13\/%e7%bb%8f%e5%85%b8dp%e4%be%8b%e9%a2%98\/","title":{"rendered":"\u7ecf\u5178dp\u4f8b\u9898"},"content":{"rendered":"

\u6b64\u6587\u7ae0\u603b\u7ed3LIS,LCS,LCIS\u7684\u5404\u79cd\u89e3\u6cd5\u53ca\u5176\u53d8\u79cd\u3002
\nLIS: Longest Increase Sequence \u6700\u5927\u4e0a\u5347\u5b50\u5e8f\u5217
\nLCS: Longest Common Sequence \u6700\u5927\u76f8\u540c\u5b50\u5e8f\u5217
\nLCIS: Longest Common Increase Sequence \u4e0a\u9762\u4e24\u4e2a\u90fd\u6709<\/p>\n

LIS<\/h3>\n

Longest Increase Sequence\uff0c\u5373\u4e00\u4e2a\u5e8f\u5217\u4e2d\u6570\u503c\u9012\u589e\u7684\u6700\u957f\u7684\u4e00\u4e2a\u5b50\u5e8f\u5217\u3002<\/p>\n

n^2\u4f5c\u6cd5<\/h4>\n

dp[i]\u8868\u793a\u4ee5a[i]\u7ed3\u5c3e\u7684\u6700\u4f18\u89e3\uff0c\u90a3\u4e48\u5bf9\u4e8edp[i]\uff0c\u626b\u63cfa[1\u2014\u2014(i-1)]\uff0c\u5728\u6240\u6709\u7684\u6bd4a[i]\u5c0f\u7684\u6570\u4e2d\uff0c\u9009\u51fadp\u6700\u5927\u7684\u4e00\u4e2a\uff0c\u52a0\u4e0a1\u5c31\u662fdp[i]\u4e86\u3002\u4e0d\u96be\u7406\u89e3\u3002<\/p>\n

\n

dp[i]=max(dp[j])+1<\/code>
\nj<i,\u4e14a[j]<a[i]<\/p>\n<\/blockquote>\n

for (int i=1;i<=n;i++){\n    dp[i] = 1;\n    for (int j=1;j<i;j++)    if (a[j]<a[i])\n        dp[i] = max(dp[i],dp[j]+1);\n}\ncout << dp[n];<\/code><\/pre>\n
\u4f46\u8fd9\u4e2a\u4e00\u822c\u7528\u4e0d\u5230\u5427\uff0c\uff0c\u592a\u7b80\u5355\u4e86\uff0c<\/p>\n
nlogn\u4f5c\u6cd5<\/h4>\n
\u5728\u4e0a\u8ff0\u505a\u6cd5\u4e2d\uff0c\u4e0d\u96be\u53d1\u73b0\u5176\u5b9e\u5c31\u662f\u66b4\u529b\u5339\u914d\uff0c\u63a5\u89e6\u4e86\u8fd9\u4e48\u591a\u7b97\u6cd5\uff0c\u5e94\u8be5\u80fd\u610f\u8bc6\u5230\u4f18\u79c0\u7684\u7b97\u6cd5\u662f\u5f88\u5c11\u505a\u65e0\u7528\u529f\u7684\u3002\u3002\u6211\u4eec\u91cd\u65b0\u5b9a\u4e49dp\u7684\u542b\u4e49\uff1adp[i]\u8868\u793a\u957f\u5ea6\u4e3ai\u7684\u4e0a\u5347\u5b50\u5e8f\u5217\u4e2d\uff0c\u7ed3\u5c3e\u7684\u6570\u662f\u591a\u5c11\u3002
\n\u8fd9\u4e2a\u5b9a\u4e49\u5f88\u91cd\u8981\uff0c\u8fd9\u6837\u4e00\u6765\uff0c\u6211\u4eec\u80fd\u60f3\u5230dp[]\u662f\u4e00\u4e2a\u6570\u503c\u4ece\u5c0f\u5230\u5927\u6392\u5217\u7684\u6570\u7ec4\uff0c\u5bf9\u4e8edp[i]\u7684\u503c\uff0c\u662f\u8d8a\u5c0f\u8d8a\u597d\u7684\uff0c\u662f\u4e00\u4e2a\u5c0f\u5c0f\u7684\u8d2a\u5fc3\u7b56\u7565\u3002\u904d\u5386\u6570\u7ec4a\uff0c\u62ff\u5230a[i]\uff0c\u5728dp\u4e2d\u4e8c\u5206\u67e5\u627e\u81ea\u5df1\u7684\u4f4d\u7f6e\uff0c\u7136\u540e\u66f4\u65b0\u5c31\u884c\u4e86\u3002<\/p>\n
\u6d1b\u8c37P1439<\/a>
\nLCS\u8f6c\u6362\u6210LIS\u518d\u6c42\u89e3\u3002<\/p>\n
#include <cstdio>\n#include <iostream>\nusing namespace std;\nconst int maxn = 1e5+5;\nint map1[maxn],map2[maxn],dp[maxn];\nint cnt=1;\nint src(int l,int r,int key);\nint main(){\n    int n,temp;\n    cin >> n;\n    for (int i=1;i<=n;i++)  {cin >> temp;map1[temp]=i;}\n    for (int i=1;i<=n;i++)  {cin >> temp;map2[map1[temp]]=i;}\n    dp[1] = map2[1];\n    for (int i=2;i<=n;i++){\n        if (map2[i]>dp[cnt]){\n            dp[++cnt] = map2[i];\n        }else{\n            dp[src(1,cnt,map2[i])] = map2[i];\n        }\n    }\n    cout << cnt;\n    return 0;\n}\nint src(int l,int r,int key){\n    if (key<dp[l])  return l;\n    if (key<dp[(l+r)\/2])    return src(l+1,(l+r)\/2,key);\n    return src((l+r)\/2+1,r,key);\n}<\/code><\/pre>\n
LCS<\/h3>\n
Longest Common Sequence
\n\u4e24\u4e2a\u5e8f\u5217\u7684\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\u3002
\n\u8fd9\u4e2a\u8c8c\u4f3c\u6ca1\u6709\u4ec0\u4e48nlogn\u7684\u4f5c\u6cd5\u3002<\/p>\n
n^2\u4f5c\u6cd5<\/h4>\n
dp[i][j]\u8868\u793aa\u5e8f\u5217\u7684\u524di\u4e2a\u5143\u7d20\u548cb\u5e8f\u5217\u7684\u524dj\u4e2a\u5143\u7d20\u7684LIS
\n\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b<\/p>\n
$$
\ndp[i][j] = \\begin{cases}dp[i-1][j-1]+1,a[i]==b[j]<\/p>\n
max(dp[i-1][j],dp[i][j-1]),a[i]!=b[j]\\end{cases}
\n$$<\/p>\n
diaonima\u7684\u8fd9\u4e2a\u63d2\u4ef6\uff0c\u6211\u8fdf\u65e9\u5378\u4e86\u4f60<\/h4>\n
for (int i=1;i<=n1;i++){\n    for (int j=1;j<=n2;j++){\n        if (a[i]==b[j]) dp[i][j] = dp[i-1][j-1]+1;\n        else    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);\n    }\n}<\/code><\/pre>\n
LCIS<\/h3>\n","protected":false},"excerpt":{"rendered":"
\u6b64\u6587\u7ae0\u603b\u7ed3LIS,LCS,LCIS\u7684\u5404\u79cd\u89e3\u6cd5\u53ca\u5176\u53d8\u79cd\u3002 LIS: Longest Increase  […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[25],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/243"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=243"}],"version-history":[{"count":24,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/243\/revisions"}],"predecessor-version":[{"id":270,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/243\/revisions\/270"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=243"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=243"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=243"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}