{"id":110,"date":"2022-12-26T20:47:04","date_gmt":"2022-12-26T12:47:04","guid":{"rendered":"https:\/\/forelink.top\/?p=110"},"modified":"2022-12-26T20:47:04","modified_gmt":"2022-12-26T12:47:04","slug":"%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%ef%bc%88week7%ef%bc%89","status":"publish","type":"post","link":"https:\/\/forelink.top\/index.php\/2022\/12\/26\/%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%ef%bc%88week7%ef%bc%89\/","title":{"rendered":"\u52a8\u6001\u89c4\u5212\uff08Week7\uff09"},"content":{"rendered":"\n

T1 \u91c7\u836f<\/h2>\n\n\n\n

\u592a\u5178\u4e86\u3002<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

\u5927\u5bb6\u95ed\u7740\u773c\u775b\u90fd\u80fd\u6572\u51fa\u6765\u3002\uff08\uff1f\uff09<\/p>\n\n\n\n

#include <iostream>\r\nusing namespace std;\r\nint T,M;\r\nint t[1005],v[1005],dp[1005];\r\nint main(){\r\n\tcin>>T>>M;\r\n\tfor(int i=1;i<=M;i++){\r\n\t\tcin>>t[i]>>v[i];\r\n\t}\r\n\t\r\n\tfor(int i=1;i<=M;i++){\r\n\t\tfor(int p=T;p>=1;p--){\r\n\t\t\tif(p>=t[i]){\r\n\t\t\t\tdp[p]=max(dp[p],dp[p-t[i]]+v[i]);\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\tcout<<dp[T];\r\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T2 \u6700\u957f\u4e0a\u5347\u5b50\u5e8f\u5217<\/h2>\n\n\n\n
\u9898\u76ee\uff1a<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u9006\u5411\u9632\u5fa1\u5bfc\u5f39\uff1f\uff09<\/p>\n\n\n\n
#include <iostream>\r\nusing namespace std;\r\nconst int N=1e6+5;\r\nint n;\r\nint num[5005];\r\nint dp[5005];\r\nint ans=1;\r\nint main(){\r\n\tcin>>n;\r\n\tfor(int i=1;i<=n;i++){\r\n\t\tcin>>num[i];\r\n\t\tfor(int j=i-1;j>=1;j--){\r\n\t\t\tif(num[j]<num[i]&&dp[i]<dp[j]+1){\r\n\t\t\t\tdp[i]=dp[j]+1;\r\n\t\t\t}\r\n\t\t}\r\n\t\tif(dp[i]==0)\r\n\t\tdp[i]=1;\r\n\t\tif(dp[i]>ans) ans=dp[i];\r\n\t}\r\n\tcout<<ans;\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T3 \u6700\u5927\u5e8f\u5217\u548c<\/h2>\n\n\n\n
\u9898\u76ee\uff1a<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u66f4\u65b0\u7684\u5f0f\u5b50\u540c\u6837\u5f88\u597d\u627e\u5230\u3002<\/p>\n\n\n\n
\u8981\u6ce8\u610f\u7684\u53ea\u662f\u5224\u65ad\u7684\u6761\u4ef6\u800c\u5df2\u3002<\/p>\n\n\n\n
#include <iostream>\r\nusing namespace std;\r\nint n,ans=-999999;\r\nint num[200005],dp[200005];\r\nint main(){\r\n\tcin>>n;\r\n\tfor(int i=1;i<=n;i++){\r\n\t\tcin>>num[i];\r\n\t\tdp[i]=num[i];\r\n\t\tif(i!=1&&dp[i-1]>=0){\r\n\t\t\tdp[i]=dp[i]+dp[i-1];\r\n\t\t}\r\n\t\tif(dp[i]>ans) ans=dp[i];\r\n\t}\r\n\tcout<<ans;\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T4 LCS<\/h2>\n\n\n\n
\u592a\u5178\u4e86\uff0c\u5567\u5567\u5567\u3002<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u4e5f\u662f\u5927\u5bb6\u95ed\u7740\u773c\u775b\u4e5f\u80fd\u6572\u51fa\u6765\u7684\u4e1c\u897f\uff08\uff1f\uff09<\/p>\n\n\n\n
#include <bits\/stdc++.h>\r\nusing namespace std;\r\nint dp[3005][3005];\r\nint max_,a1,b1;\r\nstring ans;\r\nint main(){\r\n\tstring a,b;\r\n\tgetline(cin,a);\r\n\tgetline(cin,b);\r\n\tint len1=a.length();\r\n\tint len2=b.length();\r\n\t\/\/\u77e9\u9635\u8fb9\u8fb9\u8981\u4ece0\u5f00\u59cb\uff0c\u4e0b\u68070\u4e3adp\u4e2d\u76841.\r\n\tfor(int i=0;i<len1;i++){\r\n\t\tfor(int l=0;l<len2;l++){\r\n\t\t\tif(a[i]==b[l]) dp[i+1][l+1]=dp[i][l]+1;\r\n\t\t\telse dp[i+1][l+1]=max(dp[i][l+1],dp[i+1][l]);\r\n\t\t\tif(dp[i+1][l+1]>max_){\r\n\t\t\t\tmax_=dp[i+1][l+1];\r\n\t\t\t\ta1=i+1;\r\n\t\t\t\tb1=l+1;\r\n\t\t\t}\r\n\t\t}\t\r\n\t}\r\n\twhile(a1>0&&b1>0){\r\n\t\tif(a[a1-1]==b[b1-1]){\r\n\t\t\tans=a[a1-1]+ans;\r\n\t\t\ta1-=1;\r\n\t\t\tb1-=1;\r\n\t\t}\r\n\t\telse{\r\n\t\t\tif(dp[a1-1][b1]>dp[a1][b1-1])\r\n\t\t\ta1-=1;\r\n\t\t\telse\r\n\t\t\tb1-=1;\r\n\t\t}\r\n\t}\r\n\tcout<<ans;\r\n}<\/code><\/pre>\n\n\n\n
\n","protected":false},"excerpt":{"rendered":"
T1 \u91c7\u836f \u592a\u5178\u4e86\u3002 \u5927\u5bb6\u95ed\u7740\u773c\u775b\u90fd\u80fd\u6572\u51fa\u6765\u3002\uff08\uff1f\uff09 T2 \u6700\u957f\u4e0a\u5347\u5b50\u5e8f\u5217 \u9898\u76ee\uff1a \u9006\u5411\u9632\u5fa1\u5bfc\u5f39\uff1f\uff09 T3 \u6700 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[8,3],"tags":[],"class_list":["post-110","post","type-post","status-publish","format-standard","hentry","category-8","category-3"],"_links":{"self":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/110","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/comments?post=110"}],"version-history":[{"count":1,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/110\/revisions"}],"predecessor-version":[{"id":115,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/110\/revisions\/115"}],"wp:attachment":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/media?parent=110"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/categories?post=110"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/tags?post=110"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}