{"id":34,"date":"2025-03-30T22:44:39","date_gmt":"2025-03-30T14:44:39","guid":{"rendered":"http:\/\/120.76.99.214\/?p=34"},"modified":"2025-11-24T16:43:51","modified_gmt":"2025-11-24T08:43:51","slug":"%e5%86%99%e9%a2%98%e8%ae%b0%e5%bd%95","status":"publish","type":"post","link":"https:\/\/www.tgwttt.xyz\/?p=34","title":{"rendered":"\u5199\u9898\u8bb0\u5f55"},"content":{"rendered":"\n<p>\u4eca\u5929\u8fd9\u9898\u53d6\u81ea\u4e8e\u4eca\u5929\u7684\u725b\u5ba2\u5468\u8d5bD\u9898\uff0c<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"922\" height=\"769\" src=\"http:\/\/120.76.99.214\/wp-content\/uploads\/2025\/03\/image.png\" alt=\"\" class=\"wp-image-37\" srcset=\"https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/03\/image.png 922w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/03\/image-300x250.png 300w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/03\/image-768x641.png 768w\" sizes=\"auto, (max-width: 922px) 100vw, 922px\" \/><\/figure>\n\n\n\n<pre class=\"wp-block-code\"><code>#include <iostream>\nusing namespace std;\ntypedef long long ll;\nconst int MAXN = 2e5 + 5;\nll dp[MAXN][4];\nvoid solution() {\n    int T;\n    cin >> T;\n    while (T--) {\n        int n;\n        cin >> n;\n        ll a[MAXN];\n        for (int i = 1; i <= n; i++) {\n            cin >> a[i];\n        }\n        for (int i = 0; i <= n; i++) {\n            for (int k = 0; k < 4; k++) {\n                dp[i][k] = -1e18; \n            }\n        }\n        dp[0][0] = 0; \n        for (int i = 1; i <= n; i++) {\n            for (int k = 0; k < 4; k++) {\n                if (dp[i - 1][k] != -1e18) {\n                    dp[i][k] = max(dp[i][k], dp[i - 1][k] + a[i]);\n                }\n            }\n            if (i >= 2) {\n                for (int k = 0; k < 4; k++) {\n                    if (dp[i - 2][k] != -1e18) {\n                        dp[i][k] = max(dp[i][k], dp[i - 2][k]);\n                    }\n                }\n            }\n            if (i >= 3) {\n                for (int k = 0; k < 4; k++) {\n                    if (dp[i - 3][k] != -1e18) {\n                        dp[i][k] = max(dp[i][k], dp[i - 3][k]);\n                    }\n                }\n            }\n        }\n        ll ans = -1e18;\n        for (int k = 0; k < 4; k++) {\n            ans = max(ans, dp[n][k]);\n        }\n        cout << ans << endl;\n    }\n}\n\nint main() {\n    solution();\n    return 0;\n}\n<\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"783\" height=\"726\" src=\"http:\/\/120.76.99.214\/wp-content\/uploads\/2025\/03\/image-1.png\" alt=\"\" class=\"wp-image-39\" srcset=\"https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/03\/image-1.png 783w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/03\/image-1-300x278.png 300w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/03\/image-1-768x712.png 768w\" sizes=\"auto, (max-width: 783px) 100vw, 783px\" \/><\/figure>\n\n\n\n<p>\u6d4b\u8bd5\u70b9\u90fd\u80fd\u8fc7\uff0c\u518d\u89c1\u54af\uff0c\u656c\u8bf7\u671f\u5f85\u4e0b\u6b21\u66f4\u65b0\uff01\uff01<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u4eca\u5929\u8fd9\u9898\u53d6\u81ea\u4e8e\u4eca\u5929\u7684\u725b\u5ba2\u5468\u8d5bD\u9898\uff0c \u6d4b\u8bd5\u70b9\u90fd\u80fd\u8fc7\uff0c\u518d\u89c1\u54af\uff0c\u656c\u8bf7\u671f\u5f85\u4e0b\u6b21\u66f4\u65b0\uff01\uff01<\/p>\n","protected":false},"author":1,"featured_media":39,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_kad_post_classname":"","footnotes":""},"categories":[1],"tags":[],"class_list":["post-34","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/34","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=34"}],"version-history":[{"count":7,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/34\/revisions"}],"predecessor-version":[{"id":896,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/34\/revisions\/896"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/media\/39"}],"wp:attachment":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=34"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=34"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=34"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}