{"id":32,"date":"2025-11-09T20:44:59","date_gmt":"2025-11-09T12:44:59","guid":{"rendered":"https:\/\/tblog.zeabur.app\/?p=32"},"modified":"2025-11-09T20:45:00","modified_gmt":"2025-11-09T12:45:00","slug":"%e9%a2%98%e8%a7%a3-uva1366-martian-mining","status":"publish","type":"post","link":"https:\/\/tblog.zeabur.app\/?p=32","title":{"rendered":"\u9898\u89e3 UVA1366 Martian Mining"},"content":{"rendered":"\n

\u53cc\u500d\u7ecf\u9a8c<\/a>\u3002<\/p>\n\n\n\n

\u601d\u8def<\/h2>\n\n\n\n

\u8fd9\u662f\u4e00\u9053\u7b80\u5355\u7684<\/del>\u4e8c\u7ef4\u52a8\u6001\u89c4\u5212\u95ee\u9898\uff0c\u5728\u6bcf\u4e00\u6b65\u5411\u5317\u6216\u5411\u897f\u8d70\u65f6\uff0c\u6bd4\u8f83\u5230\u8fbe\u8be5\u70b9\u65f6\uff0c\u5411\u5317\u8d70\u548c\u5411\u897f\u8d70\u8def\u4e0a\u8be5\u79cd\u77ff\u7269\u7684\u6570\u91cf\u603b\u548c\uff0c\u5e76\u53d6\u5927\u7684\u4e00\u4e2a\u3002<\/p>\n\n\n\n

\u4e3a\u4e86\u8ba1\u7b97\u66f4\u5feb\uff0c\u53ef\u4ee5\u901a\u8fc7\u5efa\u7acb $a$\uff0c$b$ \u4e24\u4e2a\u524d\u7f00\u548c\u6570\u7ec4\u6765\u8868\u793a\u8be5\u8def\u5f84\u4e0a\u4e24\u79cd\u77ff\u7269\u7684\u591a\u5c11\u3002<\/p>\n\n\n\n

\u72b6\u6001\u8f6c\u79fb<\/h3>\n\n\n\n

\u6839\u636e\u601d\u8def\uff0c\u4e0d\u96be\u5f97\u51fa\uff0c\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u4e3a\uff1a<\/p>\n\n\n\n

$$ dp[i][j]=\\max(a[i][j]+dp[i-1][j],b[i][j]+dp[i][j-1]) $$<\/p>\n\n\n\n

\u5176\u4e2d dp[i][j]<\/code> \u4ee3\u8868\u4ece $(1,1)$ \u5230 $(i,j)$ \u7684\u77e9\u9635\u4e2d\u6700\u5927\u7684\u91c7\u77ff\u91cf\uff0ca[i][j]<\/code> \u548c b[i][j]<\/code> \u5206\u522b\u4e3a A \u77ff\u548c B \u77ff\u7684\u4e8c\u7ef4\u524d\u7f00\u548c\uff0c\u8868\u793a\u91c7\u5230 $(i,j)$ \u6240\u5fc5\u987b\u7ecf\u8fc7\uff08\u5373\u9014\u4e2d\u5fc5\u987b\u91c7\u96c6\uff09\u7684\u77ff\u7269\u6570\u91cf\u603b\u548c\u3002<\/p>\n\n\n\n

\u7ed3\u675f\u6807\u5fd7\u4e3a $(n,m)$\uff0c\u5219\u7b54\u6848\u4e3a dp[n][m]<\/code>\uff0c\u8f93\u51fa\u5373\u53ef\u3002<\/p>\n\n\n\n

\u4ee3\u7801\u5b9e\u73b0<\/h2>\n\n\n\n
#include<bits\/stdc++.h>\n#include<ext\/pb_ds\/assoc_container.hpp>\n#include<ext\/pb_ds\/tree_policy.hpp>\n#define int long long\nusing namespace std;\nusing namespace __gnu_pbds;\nint n,m;\nint A[505][505],B[505][505];\/\/\u524d\u7f00\u548c\u6570\u7ec4\nint dp[505][505];\ninline void solve()\/\/dp\n{\n    for(int i=1;i<=n;i++)\n    {\n        for(int j=1;j<=m;j++)\n        {\n            dp[i][j]=max(A[i][j]+dp[i-1][j],B[i][j]+dp[i][j-1]);\/\/\u72b6\u6001\u8f6c\u79fb\n        }\n    }\n    cout<<dp[n][m];\n}\ninline void pre()\n{\n    while(cin>>n>>m and n and m)\/\/n=0 \u4e14 m=0 \u65f6\u9000\u51fa\u4e0d\u6267\u884c\n    {\n        for(int i=1;i<=n;i++)\n        {\n            for(int j=1;j<=m;j++)\n            {\n                cin>>A[i][j];\n                A[i][j]+=A[i][j-1];\/\/\u524d\u7f00\u548c\n            }\n        }\n        for(int i=1;i<=n;i++)\n        {\n            for(int j=1;j<=n;j++)\n            {\n                cin>>B[i][j];\n                B[i][j]+=B[i-1][j];\/\/\u524d\u7f00\u548c\n            }\n        }\n        solve();\n        puts(\"\");\n    }\n} \nsigned main()\n{\n    \/\/freopen(\".in\",\"r\",stdin);\n    \/\/freopen(\".out\",\"w\",stdout);\n    pre();\n    \/\/fclose(stdin);\n    \/\/fclose(stdout);\n    return 0;\n}<\/code><\/pre>\n\n\n\n
\u65f6\u95f4\u590d\u6742\u5ea6<\/strong>\uff1a$O(nm)$\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u53cc\u500d\u7ecf\u9a8c\u3002 \u601d\u8def \u8fd9\u662f\u4e00\u9053\u7b80\u5355\u7684\u4e8c\u7ef4\u52a8\u6001\u89c4\u5212\u95ee\u9898\uff0c\u5728\u6bcf\u4e00\u6b65\u5411\u5317\u6216\u5411\u897f\u8d70\u65f6\uff0c\u6bd4\u8f83\u5230\u8fbe\u8be5\u70b9\u65f6\uff0c\u5411\u5317\u8d70\u548c\u5411\u897f\u8d70\u8def\u4e0a\u8be5 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[3],"class_list":["post-32","post","type-post","status-publish","format-standard","hentry","category-oi","tag-oi"],"featured_image_src":null,"author_info":{"display_name":"CaelumRadish_c","author_link":"https:\/\/tblog.zeabur.app\/?author=1"},"_links":{"self":[{"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/posts\/32","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=32"}],"version-history":[{"count":1,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/posts\/32\/revisions"}],"predecessor-version":[{"id":33,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/posts\/32\/revisions\/33"}],"wp:attachment":[{"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=32"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=32"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=32"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}