{"id":258,"date":"2023-08-02T17:21:13","date_gmt":"2023-08-02T09:21:13","guid":{"rendered":"https:\/\/solost.cn\/?p=258"},"modified":"2023-08-02T17:21:13","modified_gmt":"2023-08-02T09:21:13","slug":"387","status":"publish","type":"post","link":"https:\/\/solost.cn\/?p=258","title":{"rendered":"2023\u725b\u5ba2\u6691\u671f\u591a\u6821\u8bad\u7ec3\u84255 – Nazrin the Greeeeeedy Mouse"},"content":{"rendered":"

\u9898\u76ee\u94fe\u63a5<\/h2>\n

\u94fe\u63a5<\/a><\/p>\n

\u9898\u76ee\u5927\u610f<\/h2>\n

\u6709n\u4e2a\u7269\u54c1\uff0cm\u4e2a\u80cc\u5305\uff08\u4f53\u79ef\u4ece\u5c0f\u5230\u5927\u7ed9\u51fa\uff09\uff0c\u6bcf\u4e2a\u7269\u54c1\u90fd\u6709\u4f53\u79ef\u548c\u4ef7\u503c\uff0c\u95eem\u4e2a\u80cc\u5305\u80fd\u88c5\u4e0b\u7269\u54c1\u7684\u6700\u5927\u4ef7\u503c\u662f\u591a\u5c11<\/p>\n

\u9898\u89e3<\/h2>\n

\/\/dpi\u4ee3\u8868\u524di\u4e2a\u80cc\u5305\u5b58\u524dr\u4e2a\u7269\u54c1\u65f6\u5019\u80fd\u6700\u5927\u4ef7\u503c<\/p>\n

\u6bcf\u589e\u52a0\u4e00\u4e2a\u80cc\u5305\uff0c\u5c31\u53ef\u4ee5\u7b97\u51fa\u80fd\u5b58\u653e\u7269\u54c1\u7684\u6700\u5927\u4ef7\u503c<\/p>\n

\u8f6c\u79fb\u65b9\u5f0f\u4e3adpi = max(dpi , dpi-1 + fl + 1[sz[i]])<\/p>\n

\/\/f[l, r, k]\u4ee3\u8868\u7f16\u53f7\u4e3al-r\u7684\u7269\u54c1\u80fd\u653e\u8fdb\u80cc\u5305\u5bb9\u91cf\u4e3ak\u65f6\u7269\u54c1\u7684\u4ef7\u503c<\/p>\n

\u8fd9\u5c31\u76f8\u5f53\u4e8e\u8f6c\u79fb\u4e86n\u6b21\u768401\u80cc\u5305<\/p>\n

\u4ee3\u7801<\/h2>\n
#include <algorithm>\n#include <bitset>\n#include <cmath>\n#include <cstdio>\n#include <cstdlib>\n#include <cstring>\n#include <fstream>\n#include <iostream>\n#include <map>\n#include <queue>\n#include <set>\n#include <stack>\n#include <unordered_map>\n#include <unordered_set>\n#include <vector>\n\n#define x first\n#define y second\n#define endl '\\n'\n#define IOS                       \\\n    ios_base::sync_with_stdio(0); \\\n    cin.tie(0);                   \\\n    cout.tie(0);\n#define fp(i, a, b) for (int i = a, i##_ = b; i <= i##_; ++i)\n#define fd(i, a, b) for (int i = a, i##_ = b; i >= i##_; --i)\n\nusing namespace std;\n\nusing ll = long long;\nusing pll = pair<ll, ll>;\nusing pii = pair<int, int>;\nusing ull = unsigned long long;\n\nconst int INF = 0x3f3f3f3f, mod = 1000000007;\nconst int N = 210, M = 2e5 + 10;\n\nll n, m;\nint a[N], b[N], sz[M];\nint f[N][N][N], dp[N][N];\n\nvoid init() {\n    fp(l, 1, n) {\n        fp(r, l, n) {\n            fp(k, 1, 200) {\n                f[l][r][k] = f[l][r - 1][k];\n                if (k >= a[r])\n                    f[l][r][k] = max(f[l][r][k], f[l][r - 1][k - a[r]] + b[r]);\n            }\n        }\n    }\n}\n\nvoid solve() {\n    cin >> n >> m;\n    fp(i, 1, n) {\n        cin >> a[i] >> b[i];\n    }\n    fp(i, 1, m) {\n        cin >> sz[i];\n    }\n    int st = max(1ll, m - n);\n    init();\n    fp(i, st, m) {\n        fp(r, 0, n) {\n            fp(l, 0, r) {\n                dp[i - st + 1][r] = max(dp[i - st + 1][r], dp[i - st][l] + f[l + 1][r][sz[i]]);\n            }\n        }\n    }\n    cout << dp[m - st + 1][n] << endl;;\n}\nint main() {\n    \/\/ IOS;\n    int _ = 1;\n    \/\/ cin >> _;\n    while (_--) {\n        solve();\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u94fe\u63a5 \u94fe\u63a5 \u9898\u76ee\u5927\u610f \u6709n\u4e2a\u7269\u54c1\uff0cm\u4e2a\u80cc\u5305\uff08\u4f53\u79ef\u4ece\u5c0f\u5230\u5927\u7ed9\u51fa\uff09\uff0c\u6bcf\u4e2a\u7269\u54c1\u90fd\u6709\u4f53\u79ef\u548c\u4ef7\u503c\uff0c\u95eem\u4e2a\u80cc\u5305\u80fd\u88c5\u4e0b\u7269\u54c1\u7684\u6700\u5927\u4ef7\u503c\u662f\u591a\u5c11 \u9898\u89e3 \/\/dpi\u4ee3\u8868\u524di\u4e2a\u80cc\u5305\u5b58\u524dr\u4e2a\u7269\u54c1\u65f6\u5019\u80fd\u6700\u5927\u4ef7\u503c \u6bcf\u589e\u52a0\u4e00\u4e2a\u80cc\u5305\uff0c\u5c31\u53ef\u4ee5\u7b97\u51fa\u80fd\u5b58\u653e\u7269\u54c1\u7684\u6700\u5927\u4ef7\u503c \u8f6c\u79fb\u65b9\u5f0f\u4e3adpi = max(dpi , dpi-1 + fl + 1[sz[i]]) \/\/f[l, r, k]\u4ee3\u8868\u7f16\u53f7\u4e3al-r\u7684\u7269\u54c1\u80fd\u653e\u8fdb\u80cc\u5305\u5bb9\u91cf\u4e3ak\u65f6\u7269\u54c1\u7684\u4ef7\u503c \u8fd9\u5c31\u76f8\u5f53\u4e8e\u8f6c\u79fb\u4e86n\u6b21\u768401\u80cc\u5305 \u4ee3\u7801 #include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <fstream> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <unordered_map> #include <unordered_set> #include <vector> #define x first #define […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[18],"class_list":["post-258","post","type-post","status-publish","format-standard","hentry","category-solution","tag-18"],"_links":{"self":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/258","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=258"}],"version-history":[{"count":0,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/258\/revisions"}],"wp:attachment":[{"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=258"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=258"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=258"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}