{"id":138,"date":"2023-05-12T22:11:11","date_gmt":"2023-05-12T14:11:11","guid":{"rendered":"https:\/\/forelink.top\/?p=138"},"modified":"2023-05-12T22:11:12","modified_gmt":"2023-05-12T14:11:12","slug":"%e4%ba%94%e9%a2%98%ef%bc%88week12%ef%bc%89","status":"publish","type":"post","link":"https:\/\/forelink.top\/index.php\/2023\/05\/12\/%e4%ba%94%e9%a2%98%ef%bc%88week12%ef%bc%89\/","title":{"rendered":"\u4e94\u9898\uff08week12\uff09"},"content":{"rendered":"\n

T1 \u6c64\u59c6\u65af\u7684\u5929\u5802\u68a6(P1796)<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <iostream>\r\nusing namespace std;\r\nconst int inf=1e9+5;\r\nint n,t,ans;\r\nint c[105][105][105],dp[105][105],planet[105];\r\n\/\/c(i,j,k)\u8868\u793a\u4ece\u7b49\u7ea7\u4e3ai\u7f16\u53f7\u4e3aj\u7684\u661f\u7403\u8d70\u5230\u7b49\u7ea7\u4e3ai+1\u7f16\u53f7\u4e3ak\u661f\u7403\u7684\u4ee3\u4ef7\r\n\/\/dp(i,j)\u8868\u793a\u8d70\u5230\u7b49\u7ea7\u4e3ai\u7f16\u53f7\u4e3aj\u7684\u661f\u7403\u7684\u4ee3\u4ef7\r\n\/\/\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff1adp(i,j)=min(dp(i-1,l)+c,dp(i,j))\r\nvoid init(){\r\n\tfor(int i=1;i<=103;i++)\r\n\tfor(int l=1;l<=103;l++)\r\n\tdp[i][l]=inf;\r\n\tfor(int i=1;i<=103;i++)\r\n\tfor(int l=1;l<=103;l++)\r\n\tfor(int k=1;k<=103;k++)\r\n\tc[i][l][k]=inf;\r\n\tplanet[0]=1;\r\n}\r\nint main(){\r\n\tinit();\r\n\tcin>>n;\r\n\tfor(int i=1;i<=n;i++){\r\n\t\tcin>>t;\r\n\t\tplanet[i]=t;\r\n\t\tint cnt=1;\r\n\t\twhile(t--){\r\n\t\t\tint st,v,z;\r\n\t\t\tcin>>st>>v>>z;\r\n\t\t\tc[i-1][st][cnt]=v;\r\n\t\t\twhile(z!=0){\r\n\t\t\t\tst=z;\r\n\t\t\t\tcin>>v>>z;\r\n\t\t\t\tif(c[i-1][st][cnt]>v)\/\/\u4f60\u5988\u7684\u6709\u91cd\u8fb9\r\n\t\t\t\tc[i-1][st][cnt]=v;\r\n\t\t\t}\r\n\t\t\tcnt++;\/\/\u5230\u8fbe\u7684\u7b49\u7ea7\u4e3ai\u7684\u661f\u7403\u7f16\u53f7\r\n\t\t}\r\n\t}\r\n\tdp[0][1]=0;\r\n\tfor(int i=1;i<=n;i++){\r\n\t\tfor(int l=1;l<=planet[i];l++){\r\n\t\t\tfor(int k=1;k<=planet[i-1];k++){\r\n\t\t\t\tif(c[i-1][k][l]==inf) continue;\r\n\t\t\t\tdp[i][l]=min(dp[i][l],dp[i-1][k]+c[i-1][k][l]);\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\tans=inf;\r\n\tfor(int i=1;i<=planet[n];i++)\r\n\tans=min(ans,dp[n][i]);\r\n\tcout<<ans;\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T2 \u8dd1\u6b65\uff08P1806\uff09<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include<iostream>\r\nusing namespace std;\r\nlong long int n,ans,dp[505][505];\r\nvoid init(){\r\n\tfor(int i=1;i<3;i++)\r\n\tfor(int l=1;l<=500;l++)\r\n\tdp[i][l]=0;\r\n}\r\nlong long int sum_(int row,int x){\r\n\tlong long int sum=0;\r\n\tfor(int k=x;k<=500;k++)\r\n\tsum+=dp[row][k];\r\n\treturn sum;\r\n}\r\nint main(){\r\n\tcin>>n;\r\n\tfor(int i=1;i<=500;i++){\r\n\t\tfor(int l=1;l<=500;l++){\r\n\t\t\tif((i%2!=0&&l>i\/2)||(i%2==0&&l>=i\/2)) break;\r\n\t\t\tdp[i][l]=sum_(i-l,l+1)+1;\r\n\t\t}\r\n\t}\r\n\tfor(int i=1;i<=500;i++)\r\n\tans+=dp[n][i];\r\n\tcout<<ans;\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T3 \u781d\u7801\u79f0\u91cd(P8742)<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <iostream>\r\n#include <cmath>\r\nusing namespace std;\r\nint n,w[105],max_,ans;\r\nbool dp[105][300005];\r\nvoid prework(){\r\n\tcin>>n;\r\n\tfor(int i=1;i<=n;i++)\r\n\t{\r\n\t\tcin>>w[i];\r\n\t\tmax_=max_+w[i];\r\n\t}\r\n\tdp[0][0]=1;\r\n}\r\nvoid solve(){\r\n\tfor(int i=1;i<=n;i++){\r\n\t\tfor(int l=1;l<=max_;l++){\r\n\t\t\tdp[i][l]=dp[i-1][l];\r\n\t\t\tif(w[i]==l) \r\n\t\t\tdp[i][l]=1;\r\n\t\t\telse if(dp[i-1][l+w[i]]==1)\r\n\t\t\tdp[i][l]=1;\r\n\t\t\telse if(dp[i-1][abs(l-w[i])]==1)\r\n\t\t\tdp[i][l]=1;\r\n\t\t\tif(dp[n][l]==1) ans++;\r\n\t\t}\r\n\t}\r\n\tcout<<ans;\r\n}\r\nint main(){\r\n\tprework();\r\n\tsolve();\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T4 \u9057\u5740\uff08P1959\uff09<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <iostream>\r\n#include <cmath>\r\nusing namespace std;\r\nstruct edge{\r\n\tint x,y;\r\n}a[3005];\r\nint n,ans;\r\nbool vis[5005][5005];\r\nvoid check(int x1,int y1,int x2,int y2){\r\n\tint yy=abs(y1-y2);\r\n\tint xx=abs(x1-x2);\r\n\tint x3=x2+yy;\r\n\tint y3=y2+xx;\r\n\tint x4=x1+yy;\r\n\tint y4=y1+xx;\r\n\tif(x3<=5000&&y3<=5000&&x4<=5000&&y4<=5000&&vis[x3][y3]&&vis[x4][y4]){\r\n\t\tint temp=xx*xx+yy*yy;\r\n\t\tif(temp>ans) ans=temp;\r\n\t}\r\n\tx3=x2-yy;\r\n\ty3=y2-xx;\r\n\tx4=x1-yy;\r\n\ty4=y1-xx;\r\n\tif(x3>=0&&y3>=0&&x4>=0&&y4>=0&&vis[x3][y3]&&vis[x4][y4]){\r\n\t\tint temp=xx*xx+yy*yy;\r\n\t\tif(temp>ans) ans=temp;\r\n\t}\r\n}\r\nint main(){\r\n\tcin>>n;\r\n\tfor(int i=1;i<=n;i++){\r\n\t\tint xx,yy;\r\n\t\tcin>>xx>>yy;\r\n\t\tvis[xx][yy]=true;\r\n\t\ta[i].x=xx;\r\n\t\ta[i].y=yy;\r\n\t}\/\/\u8bfb\u5165\u6570\u636e\r\n\tfor(int i=1;i<=n;i++){\r\n\t\tfor(int j=1;j<i;j++){\r\n\t\t\tcheck(a[i].x,a[i].y,a[j].x,a[j].y);\r\n\t\t}\r\n\t}\r\n\tcout<<ans;\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T5 \u73af\u5883\u6cbb\u7406\uff08P8794\uff09<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <iostream>\r\nusing namespace std;\r\nint n,q,max,cnt;\r\nint map[105][105],work[105][105];\r\nint lmt[105][105];\r\nbool checklmt(){\r\n\tfor(int i=0;i<n;i++)\r\n\tfor(int l=0;l<n;l++)\r\n\twork[i][l]=lmt[i][l];\r\n\tfor(int k=0;k<n;k++)\r\n\t\tfor(int i=0;i<n;i++)\r\n\t\t\tfor(int l=0;l<n;l++){\r\n\t\t\t\tif(i==l) continue;\r\n\t\t\t\tif(work[i][l]>work[k][l]+work[i][k])\r\n\t\t\t\twork[i][l]=work[k][l]+work[i][k];\r\n\t\t\t\t}\r\n\tint sum_=0;\r\n\tfor(int i=0;i<n;i++)\r\n\tfor(int l=0;l<n;l++)\r\n\tsum_+=work[i][l];\r\n\tif(sum_<=q) return true;\r\n\treturn false;\r\n}\r\nvoid init(){\r\n\tfor(int i=0;i<n;i++)\r\n\tfor(int l=0;l<n;l++)\r\n\twork[i][l]=map[i][l];\r\n}\r\nint sum(){\r\n\tint ans=0;\/\/\u52a0\u548c\u524d\u521d\u59cb\u5316\r\n\tfor(int i=0;i<n;i++)\r\n\t\tfor(int l=0;l<n;l++)\r\n\t\tans+=work[i][l];\r\n\t\treturn ans;\r\n}\r\nvoid prework(){\r\n\tcin>>n>>q;\r\n\tfor(int i=0;i<n;i++)\r\n\t\tfor(int l=0;l<n;l++)\r\n\t\t\tcin>>map[i][l];\r\n\tfor(int i=0;i<n;i++)\r\n\t\tfor(int l=0;l<n;l++)\r\n\t\t\tcin>>lmt[i][l];\r\n}\r\nbool floyd(){\r\n\tinit();\/\/\u521d\u59cb\u5316\r\n\tfor(int k=0;k<n;k++)\r\n\t\tfor(int i=0;i<n;i++)\r\n\t\t\tfor(int l=0;l<n;l++){\r\n\t\t\t\tif(i==l) continue;\r\n\t\t\t\tif(work[i][l]>work[k][l]+work[i][k])\r\n\t\t\t\twork[i][l]=work[k][l]+work[i][k];\r\n\t\t\t}\r\n\t\t\tif(sum()<=q) return false;\r\n\t\t\treturn true;\r\n}\r\nvoid solve(){\r\n\twhile(floyd()){\r\n\t\tint row=cnt%n;\r\n\t\tfor(int i=0;i<n;i++){\r\n\t\t\tif(map[row][i]>lmt[row][i])\r\n\t\t\tmap[row][i]--;\r\n\t\t}\r\n\t\tcnt++;\r\n\t}\r\n\tcout<<cnt;\r\n}\r\nint main(){\r\n\tprework();\r\n\tif(!checklmt()){\r\n\t\tcout<<\"-1\";\r\n\t\treturn 0;\r\n\t}\r\n\tsolve();\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\n","protected":false},"excerpt":{"rendered":"
T1 \u6c64\u59c6\u65af\u7684\u5929\u5802\u68a6(P1796) T2 \u8dd1\u6b65\uff08P1806\uff09 T3 \u781d\u7801\u79f0\u91cd(P8742) T4 \u9057\u5740\uff08P19 […]<\/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":[3,1],"tags":[],"class_list":["post-138","post","type-post","status-publish","format-standard","hentry","category-3","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/138","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=138"}],"version-history":[{"count":1,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/138\/revisions"}],"predecessor-version":[{"id":144,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/138\/revisions\/144"}],"wp:attachment":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/media?parent=138"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/categories?post=138"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/tags?post=138"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}