{"id":103,"date":"2022-12-26T20:36:39","date_gmt":"2022-12-26T12:36:39","guid":{"rendered":"https:\/\/forelink.top\/?p=103"},"modified":"2022-12-26T20:37:02","modified_gmt":"2022-12-26T12:37:02","slug":"%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%ef%bc%88week8%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%88week8%ef%bc%89\/","title":{"rendered":"\u52a8\u6001\u89c4\u5212\uff08Week8\uff09"},"content":{"rendered":"\n

T1 \u75af\u72c2\u7684\u91c7\u836f<\/h2>\n\n\n\n

\u9898\u76ee\uff1a<\/p>\n\n\n\n

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

\u662f\u7ecf\u5178\u768401\u80cc\u5305\u95ee\u9898\uff0c\u5728\u535a\u5ba2\u53e6\u4e00\u5904\u6709\u4ecb\u7ecd\uff0c\u63a8\u51fa \u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u5373\u53ef\u3002<\/p>\n\n\n\n

\u4ee3\u7801\u5982\u4e0b\u3002<\/p>\n\n\n\n

#include <iostream>\nusing namespace std;\nlong long int T,n;\nlong long int t[10005],w[10005];\nlong long int dp[10000005];\nint main(){\n\tcin>>T>>n;\n\tfor(int i=1;i<=n;i++) \n\tcin>>t[i]>>w[i];\n\tfor(int i=1;i<=n;i++){\n\t\tfor(int l=1;l<=T;l++){\n\t\t\tif(l>=t[i])\n\t\t\tdp[l]=max(dp[l],dp[l-t[i]]+w[i]);\n\t\t}\n\t}\n\tcout<<dp[T];\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T2 \u6446\u82b1<\/h2>\n\n\n\n
\u9898\u76ee\uff1a<\/p>\n\n\n\n
\u8ba1\u6570dp<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u7528\u586b\u8868\u6cd5\u7684\u601d\u60f3\u53ef\u4ee5\u5f97\u51fa\u66f4\u65b0dp\u6570\u7ec4\u7684\u5f0f\u5b50\u3002<\/p>\n\n\n\n
#include <iostream>\nusing namespace std;\nconst long long int x=1000007;\nlong long int n,m,a[104],dp[105][105];\n\/\/dp[i][j]\u8bb0\u5f55\u6709i\u79cd\u82b1\uff0c\u8981\u6446j\u76c6\u65f6\u7684\u6446\u6cd5\u3002\nint main(){\n\tdp[0][0]=1;\/\/\u4e00\u79cd\u82b1\u90fd\u6ca1\u6709\u7684\u8bdd\u662f\u4e00\u79cd\u60c5\u51b5\u3002\n\tcin>>n>>m;\n\tfor(long long int i=1;i<=n;i++)\n\tcin>>a[i];\n\tfor(long long int i=1;i<=n;i++){\n\t\tfor(long long int l=0;l<=m;l++){\n\t\t\tfor(long long int p=0;p<=min(l,a[i]);p++){\n\t\t\t\tdp[i][l]=(dp[i][l]+dp[i-1][l-p])%x;\/\/\u6bcf\u6b21\u90fd\u53d6\u6a21\u3002\n\t\t\t}\n\t\t}\n\t}\n\tcout<<dp[n][m];\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T3 \u6a31\u82b1<\/h2>\n\n\n\n
\u9898\u76ee\uff1a<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u770b\u9898\u53ef\u4ee5\u77e5\u9053\u6709\u4e9b\u7f8e\u5b66\u503c\u662f\u53ef\u4ee5\u62ff\u5f88\u591a\u751a\u81f3\u65e0\u9650\u6b21\u7684\uff0c\u6240\u4ee5\u8fd9\u662f\u4e00\u4e2a\u591a\u91cd\u80cc\u5305\u95ee\u9898\uff0c\u53ef\u4ee5\u7528\u4e8c\u8fdb\u5236\u4f18\u5316\u5c06\u590d\u6742\u5ea6\u7531O\uff08n^3\uff09\u4f18\u5316\u81f3O\uff08n^2 logn\uff09<\/p>\n\n\n\n
\u53ef\u4ee5\u628a\u6ca1\u6709\u6b21\u6570\u9650\u5236\u7684\u7f8e\u5b66\u503c\u6b21\u6570\u8bbe\u6210\u4e00\u4e2a\u6bd4\u8f83\u5927\u7684\u6570\u3002<\/p>\n\n\n\n
\u4ee3\u7801\u5982\u4e0b\u3002<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nint N,V;\nint v[100000005],w[100000006],dp[100000005];\nlong long int hs,ms,he,me;\nint main(){\n\tscanf(\"%lld:%lld %lld:%lld %lld\",&hs,&ms,&he,&me,&N);\n\the-=hs;\n\tif(me-ms<0)\n\tme=me-ms+60,he--,me+=he*60;\n\telse me = me - ms + he * 60;\n\tV=me;\n\tint count=0;\n\t\/\/\u5206\u62102^0(1),2^1(2),2^2(4),2^3(8)...\u4f59\u6570\u7ec4\u3002\n\t\/\/O(n^3)->O(n^2logS\uff09\n\tfor(int i=1;i<=N;++i){\n\t\tint z,x,c;\n\t\tcin>>z>>x>>c;\n\t\tif(c==0) c=9999999;\n\t\tfor(int k=1;k<=c;k*=2){\n\t\t\tcount++;\n\t\t\tv[count]=z*k;\n\t\t\tw[count]=x*k;\n\t\t\tc-=k;\n\t\t}\n\t\tif(c>0){\n\t\t\tcount++;\n\t\t\tv[count]=z*c;\n\t\t\tw[count]=x*c;\n\t\t}\n\t}\n\tfor(int i=1;i<=count;++i){\n\t\tfor(int k=V;k>=0;k--){\n\t\t\tif(k>=v[i])\n\t\t\tdp[k]=max(dp[k],dp[k-v[i]]+w[i]);\n\t\t}\n\t}\n\tcout<<dp[V];\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T4 \u91d1\u660e\u7684\u9884\u7b97\u65b9\u6848<\/h2>\n\n\n\n
\u9898\u76ee\uff1a<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u8fd9\u9898\u5b58\u9644\u4ef6\u6570\u636e\u6280\u5de7\u662f\u5f00\u4e8c\u7ef4\u6570\u7ec4cost[x][y],x\u4e3a\u7b2cx\u4ef6\u7269\u54c1\uff0c\u5f53y\u4e3a0\u65f6\u4e3a\u8fd9\u4ef6\u7269\u54c1\u672c\u8eab\uff0cy\u4e3a1\u65f6\u4e3a\u7b2cx\u4ef6\u7269\u54c1\u7684\u9644\u4ef61\uff0cy\u4e3a2\u65f6\u4e3a\u7b2cx\u4ef6\u7269\u54c1\u7684\u9644\u4ef62\u3002<\/p>\n\n\n\n
\u7136\u540e\u6bcf\u6b21\u9009\u62e9\u6709\u4e94\u79cd\u60c5\u51b5\uff0c<\/p>\n\n\n\n
\u2460\u53ea\u4e70\u4e3b\u4ef6
\u2461\u4e70\u4e3b\u4ef6+\u9644\u4ef61
\u2462\u4e70\u4e3b\u4ef6+\u9644\u4ef62
\u2463\u4e70\u4e3b\u4ef6+\u9644\u4ef61+\u9644\u4ef62
\u2464\u4e0d\u4e70\u4e3b\u4ef6\u3002<\/p>\n\n\n\n
\u9664\u4e861\u548c5\u51b2\u7a81\u5916\uff0c\u5176\u4ed6\u56db\u4e2a\u90fd\u80fd\u5224\u65ad\u540e\u66f4\u65b0\u65b0\u7684dp\u503c\uff0c\u987a\u5e8f\u4efb\u610f\uff0c\u679a\u4e3e\u8fd9\u4e94\u79cd\u60c5\u51b5\uff0c\u586b\u8868\u5373\u53ef\u3002<\/p>\n\n\n\n
\u4ee3\u7801\u5982\u4e0b\u3002<\/p>\n\n\n\n
#include <iostream>\n#include <cstring>\nusing namespace std;\nint m,n;\nint dp[70][40000];\nint cost[70][5],imp[70][5];\nint main(){\n\tcin>>m>>n;\n\tint c,im,f;\n\tfor(int i=1;i<=n;i++){\n\t\tcin>>c>>im>>f;\n\t\tif(!f){\n\t\t\tcost[i][0]=c;\n\t\t\timp[i][0]=im;\n\t\t}\n\t\telse{\n\t\t\tif(!cost[f][1]){\n\t\t\t\tcost[f][1]=c;\n\t\t\t\timp[f][1]=im;\n\t\t\t}\n\t\t\telse{\n\t\t\t\tcost[f][2]=c;\n\t\t\t\timp[f][2]=im;\n\t\t\t}\n\t\t}\n\t}\n\tmemset(dp,0,sizeof(dp));\n\tfor(int i=1;i<=n;i++){\n\t\tfor(int l=1;l<=m;l++){\n\t\t\tif(l-cost[i][0]>=0){\n\t\t\t\tdp[i][l]=max(dp[i-1][l],dp[i-1][l-cost[i][0]]+cost[i][0]*imp[i][0]);\n\t\t\t\tif(l-cost[i][0]-cost[i][1]>=0){\n\t\t\t\tdp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][1]]+cost[i][0]*imp[i][0]+cost[i][1]*imp[i][1]);\n\t\t\t\t}\n\t\t\t\tif(l-cost[i][0]-cost[i][2]>=0){\n\t\t\t\tdp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][2]]+cost[i][0]*imp[i][0]+cost[i][2]*imp[i][2]);\n\t\t\t\t}\n\t\t\t\tif(l-cost[i][0]-cost[i][1]-cost[i][2]>=0){\n\t\t\t\t\tdp[i][l]=max(dp[i][l],dp[i-1][l-cost[i][0]-cost[i][1]-cost[i][2]]+cost[i][0]*imp[i][0]+cost[i][1]*imp[i][1]+cost[i][2]*imp[i][2]);\n\t\t\t\t}\n\t\t\t}\n\t\t\telse\n\t\t\tdp[i][l]=dp[i-1][l];\n\t\t}\n\t}\n\tcout<<dp[n][m];\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
\u603b\u7ed3\uff1a<\/h2>\n\n\n\n
\u8bb0\u5fc6\u5316\u641c\u7d22>dp\uff1f\uff09\u3002
\u4ee3\u7801\u5199\u7684\u597d\u4e11\u5440\u3002\uff08\u4e0d\u662f\u4ec0\u4e48\u5927\u95ee\u9898\u5c31\u662f\uff09<\/p>\n","protected":false},"excerpt":{"rendered":"
T1 \u75af\u72c2\u7684\u91c7\u836f \u9898\u76ee\uff1a \u662f\u7ecf\u5178\u768401\u80cc\u5305\u95ee\u9898\uff0c\u5728\u535a\u5ba2\u53e6\u4e00\u5904\u6709\u4ecb\u7ecd\uff0c\u63a8\u51fa \u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u5373\u53ef\u3002 \u4ee3\u7801\u5982\u4e0b\u3002 T2 […]<\/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-103","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\/103","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=103"}],"version-history":[{"count":2,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/103\/revisions"}],"predecessor-version":[{"id":109,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/103\/revisions\/109"}],"wp:attachment":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/media?parent=103"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/categories?post=103"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/tags?post=103"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}