{"id":84,"date":"2026-03-31T22:23:25","date_gmt":"2026-03-31T14:23:25","guid":{"rendered":"https:\/\/geocommunity.vip\/?p=84"},"modified":"2026-03-31T22:52:37","modified_gmt":"2026-03-31T14:52:37","slug":"%e8%93%9d%e6%a1%a5%e6%9d%af%e7%ae%97%e6%b3%95%e6%a8%a1%e6%9d%bf","status":"publish","type":"post","link":"https:\/\/geocommunity.vip\/index.php\/2026\/03\/31\/%e8%93%9d%e6%a1%a5%e6%9d%af%e7%ae%97%e6%b3%95%e6%a8%a1%e6%9d%bf\/","title":{"rendered":"\u84dd\u6865\u676f\u7b97\u6cd5\u6a21\u677f\uff08D\uff09"},"content":{"rendered":"\n

1\u3001\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217<\/h3>\n\n\n\n

\uff081\uff09\u9898\u76ee\u63cf\u8ff0\uff1a<\/strong>\u7ed9\u5b9a\u4e00\u4e2a\u6574\u6570\u6570\u7ec4 nums<\/code>\uff0c\u627e\u5230\u5176\u4e2d\u6700\u957f\u4e25\u683c\u9012\u589e\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\u3002<\/p>\n\n\n\n

\uff082\uff09\u7b97\u6cd5\u601d\u8def\uff1a<\/strong>\u52a8\u6001\u89c4\u5212\uff0cdp[i]<\/code> \u8868\u793a\u4ee5 nums[i]<\/code> \u7ed3\u5c3e\u7684\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u957f\u5ea6\u3002<\/p>\n\n\n\n

\uff083\uff09\u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n

#define MAX(a, b) ((a) > (b) ? (a) : (b))\n\nint lengthOfLIS(int* nums, int numsSize) {\n    \/\/ \u52a8\u6001\u5f00\u8f9f\u5185\u5b58\u4e0e\u521d\u59cb\u5316\n    int *dp = (int *)malloc(numsSize * sizeof(int));\n    for (int i = 0; i < numsSize; i++) {\n        dp[i] = 1;\n    }\n\n    \/\/ \u52a8\u6001\u89c4\u5212\n    for (int i = 0; i < numsSize; i++) {\n        for (int j = 0; j < i; j++) {\n            if (nums[j] < nums[i]) {\n                dp[i] = MAX(dp[i], dp[j] + 1);\n            }\n        }\n    }\n\n    \/\/ \u627e\u6700\u5927\u503c\n    int ans = 0;\n    for (int i = 0; i < numsSize; i++) {\n        ans = MAX(ans, dp[i]);\n    }\n\n    free(dp);\n    return ans;\n}<\/code><\/pre>\n\n\n\n
2\u3001\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217<\/h3>\n\n\n\n
\uff081\uff09\u9898\u76ee\u63cf\u8ff0<\/strong>\uff1a\u7ed9\u5b9a\u4e24\u4e2a\u5b57\u7b26\u4e32 text1<\/code> \u548c text2<\/code>\uff0c\u8fd4\u56de\u5b83\u4eec\u7684\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\u957f\u5ea6\u3002<\/p>\n\n\n\n
\uff082\uff09\u7b97\u6cd5\u601d\u8def<\/strong>\uff1a\u4e8c\u7ef4\u52a8\u6001\u89c4\u5212\uff0cdp[i][j]<\/code> \u8868\u793a text1<\/code> \u524d i<\/code> \u4e2a\u5b57\u7b26\u4e0e text2<\/code> \u524d j<\/code> \u4e2a\u5b57\u7b26\u7684\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\u957f\u5ea6\u3002<\/p>\n\n\n\n
\uff08<\/strong>3\uff09\u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n
#include <string.h>\n#include <stdlib.h>\n\nint longestCommonSubsequence(char* text1, char* text2) {\n    int n = strlen(text1);\n    int m = strlen(text2);\n\n    \/\/ \u7533\u8bf7 dp \u6570\u7ec4\n    int **dp = (int **)malloc((n + 1) * sizeof(int *));\n    for (int i = 0; i <= n; i++) {\n        dp[i] = (int *)malloc((m + 1) * sizeof(int));\n    }\n\n    \/\/ \u521d\u59cb\u5316\n    for (int i = 0; i <= n; i++) {\n        for (int j = 0; j <= m; j++) {\n            dp[i][j] = 0;\n        }\n    }\n\n    \/\/ \u52a8\u6001\u89c4\u5212\n    for (int i = 1; i <= n; i++) {\n        for (int j = 1; j <= m; j++) {\n            if (text1[i - 1] == text2[j - 1]) {\n                dp[i][j] = dp[i - 1][j - 1] + 1;\n            } else {\n                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];\n            }\n        }\n    }\n\n    int ans = dp[n][m];\n\n    \/\/ \u91ca\u653e\u5185\u5b58\n    for (int i = 0; i <= n; i++) {\n        free(dp[i]);\n    }\n    free(dp);\n\n    return ans;\n}<\/code><\/pre>\n\n\n\n
3\u3001\u4e8c\u7ef4\u524d\u7f00\u548c\u4e0e\u5dee\u5206\u6570\u7ec4<\/h3>\n\n\n\n
\uff081\uff09\u9898\u76ee\u63cf\u8ff0<\/strong>\uff1a\u7ed9\u5b9a n \u00d7 m<\/code> \u7684\u77e9\u9635\uff0c\u8fdb\u884c q<\/code> \u6b21\u533a\u95f4\u4fee\u6539\uff0c\u6bcf\u6b21\u5bf9\u5b50\u77e9\u9635 [x1,y1]<\/code> \u5230 [x2,y2]<\/code> \u52a0\u4e0a c<\/code>\uff0c\u8f93\u51fa\u6700\u7ec8\u77e9\u9635\u3002<\/p>\n\n\n\n
\uff082\uff09\u7b97\u6cd5\u601d\u8def<\/strong>\uff1a\u5229\u7528\u4e8c\u7ef4\u5dee\u5206\u6570\u7ec4\u5b9e\u73b0 O(1) \u533a\u95f4\u4fee\u6539\u3002<\/p>\n\n\n\n
\uff083\uff09\u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n
#include <stdio.h>\n\n#define MAXN 1005   \/\/ \u53ef\u6839\u636e\u9898\u76ee\u6700\u5927\u8303\u56f4\u8c03\u6574\n#define MAXM 1005\n\nlong long a[MAXN][MAXM];\nlong long diff[MAXN][MAXM];\n\nint main() {\n    int n, m, q;\n    scanf(\"%d %d %d\", &n, &m, &q);\n\n    \/\/ \u8bfb\u5165\u539f\u6570\u7ec4 a\uff08\u4ece 1 \u5f00\u59cb\uff09\n    for (int i = 1; i <= n; i++) {\n        for (int j = 1; j <= m; j++) {\n            scanf(\"%lld\", &a[i][j]);\n        }\n    }\n\n    \/\/ \u6784\u5efa\u4e8c\u7ef4\u5dee\u5206\u6570\u7ec4\n    for (int i = 1; i <= n; i++) {\n        for (int j = 1; j <= m; j++) {\n            diff[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];<\/strong>\n        }\n    }\n\n    \/\/ \u5904\u7406 q \u6b21\u533a\u95f4\u4fee\u6539\n    while (q--) {\n        int x1, y1, x2, y2;\n        long long c;\n        scanf(\"%d %d %d %d %lld\", &x1, &y1, &x2, &y2, &c);\n\n        diff[x1][y1]       += c;\n       diff[x2 + 1][y1]   -= c;\n       diff[x1][y2 + 1]   -= c;\n       diff[x2 + 1][y2 + 1] += c;<\/strong>\n    }\n\n    \/\/ \u7531\u5dee\u5206\u6570\u7ec4\u8fd8\u539f\u6700\u7ec8\u6570\u7ec4 a\n    for (int i = 1; i <= n; i++) {\n        for (int j = 1; j <= m; j++) {\n            a[i][j] = diff[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];<\/strong>\n        }\n    }\n\n    \/\/ \u8f93\u51fa\u7ed3\u679c\n    for (int i = 1; i <= n; i++) {\n        for (int j = 1; j <= m; j++) {\n            printf(\"%lld \", a[i][j]);\n        }\n        printf(\"\\n\");\n    }\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n
4\u3001\u4e00\u7ef4\u524d\u7f00\u548c\u4e0e\u5dee\u5206\u6570\u7ec4<\/h3>\n\n\n\n
\uff081\uff09\u9898\u76ee\u63cf\u8ff0<\/strong>\uff1a\u7ed9\u5b9a\u957f\u5ea6\u4e3a n<\/code> \u7684\u6570\u7ec4\uff0c\u8fdb\u884c q<\/code> \u6b21\u533a\u95f4\u52a0\u64cd\u4f5c\uff0c\u8f93\u51fa\u6700\u7ec8\u6570\u7ec4\u3002<\/p>\n\n\n\n
\uff082\uff09\u7b97\u6cd5\u601d\u8def<\/strong>\uff1a\u5229\u7528\u4e00\u7ef4\u5dee\u5206\u6570\u7ec4\u5b9e\u73b0 O(1) \u533a\u95f4\u4fee\u6539\u3002<\/p>\n\n\n\n
\uff083\uff09\u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n
#include <stdio.h>\n\n#define MAXN 100005\n\nlong long a[MAXN];\nlong long diff[MAXN]; \/\/ \u5168\u5c40\u5b9a\u4e49 \u7b49\u540c\u4e8elong long diff[MAXN] = {0};<\/strong>\nlong long temp[MAXN];\n\nint main() {\n    int n, q;\n    scanf(\"%d %d\", &n, &q);\n\n    \/\/ \u8bfb\u5165\u539f\u6570\u7ec4 a\n    for (int i = 1; i <= n; i++) {\n        scanf(\"%lld\", &a[i]);\n    }\n\n    \/\/ \u5904\u7406 q \u6b21\u533a\u95f4\u52a0\n    while (q--) {\n        int l, r;\n        long long c;\n        scanf(\"%d %d %lld\", &l, &r, &c);\n\n        diff[l] += c;\n        \/\/ \u5148\u786e\u4fdd\u4e0d\u8d8a\u754c\n        if (r + 1 <= n) {\n            diff[r + 1] -= c;\n        }<\/strong>\n    }\n\n    \/\/ \u8fd8\u539f\u5dee\u5206\u503c\n    for (int i = 1; i <= n; i++) {\n        temp[i] = temp[i - 1] + diff[i];<\/strong>\n    }\n\n    \/\/ \u8f93\u51fa\u7ed3\u679c\uff08\u539f\u6570\u7ec4 + \u5dee\u5206\u7d2f\u52a0\u503c\uff09\n    for (int i = 1; i <= n; i++) {\n        printf(\"%lld \", a[i] + temp[i]);\n    }\n    printf(\"\\n\");\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n
5\u30010-1\u80cc\u5305<\/h3>\n\n\n\n
\uff081\uff09\u9898\u76ee\u63cf\u8ff0<\/strong>\uff1a\u6709 n<\/code> \u4ef6\u7269\u54c1\uff0c\u6bcf\u4ef6\u7269\u54c1\u91cd\u91cf\u4e3a w<\/code>\uff0c\u4ef7\u503c\u4e3a v<\/code>\uff0c\u80cc\u5305\u5bb9\u91cf\u4e3a V<\/code>\uff0c\u6bcf\u4ef6\u7269\u54c1\u6700\u591a\u9009\u4e00\u6b21\uff0c\u6c42\u6700\u5927\u4ef7\u503c\u3002<\/p>\n\n\n\n
\uff082\uff09\u4e8c\u7ef4DP\u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n
#include <stdio.h>\n\nint main() {\n    int n, V;\n    scanf(\"%d %d\", &n, &V);\n\n    \/\/ dp[i][j]\uff1a\u53ea\u8003\u8651\u524d i \u4e2a\u7269\u54c1\uff0c\u80cc\u5305\u5bb9\u91cf\u4e3a j \u65f6\u7684\u6700\u5927\u4ef7\u503c<\/strong>\n    int dp[n + 1][V + 1];\n\n    \/\/ \u521d\u59cb\u5316\n    for (int i = 0; i <= n; i++) {\n        for (int j = 0; j <= V; j++) {\n            dp[i][j] = 0;\n        }\n    }\n\n    for (int i = 1; i <= n; i++)<\/strong> {\n        int w, v;\n        scanf(\"%d %d\", &w, &v);\n\n        for (int j = 1; j <= V; j++)<\/strong> {\n            if (j >= w) {\n                \/\/ \u9009 or \u4e0d\u9009\n                int not_take = dp[i - 1][j];\n                int take = dp[i - 1][j - w] + v;\n                dp[i][j] = not_take > take ? not_take : take;\n            } else {\n                \/\/ \u88c5\u4e0d\u4e0b\uff0c\u53ea\u80fd\u4e0d\u9009\n                dp[i][j] = dp[i - 1][j];\n            }\n        }\n    }\n\n    printf(\"%d\\n\", dp[n][V]);\n    return 0;\n}<\/code><\/pre>\n\n\n\n
\uff083\uff09\u4e00\u7ef4DP\u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n\nint main() {\n    int n, V;\n    scanf(\"%d %d\", &n, &V);\n\n    \/\/ dp[j]\uff1a\u80cc\u5305\u5bb9\u91cf\u4e3a j \u65f6\u7684\u6700\u5927\u4ef7\u503c\n    int *dp = (int *)malloc((V + 1) * sizeof(int));\n\n    \/\/ \u521d\u59cb\u5316\u4e3a 0\n    for (int j = 0; j <= V; j++) {\n        dp[j] = 0;\n    }\n\n    for (int i = 1; i <= n; i++)<\/strong> {\n        int w, v;\n        scanf(\"%d %d\", &w, &v);\n\n        \/\/ \u26a0\ufe0f \u5173\u952e\uff1a\u5bb9\u91cf\u5fc5\u987b\u4ece\u5927\u5230\u5c0f\u904d\u5386\n        for (int j = V; j >= w; j--)<\/strong> {\n            int not_take = dp[j]<\/strong>;\n            int take = dp[j - w] + v<\/strong>;\n            dp[j] = not_take > take ? not_take : take;\n        }\n    }\n\n    printf(\"%d\\n\", dp[V]);\n\n    free(dp);\n    return 0;\n}<\/code><\/pre>\n\n\n\n
6\u3001\u5b8c\u5168\u80cc\u5305<\/h3>\n\n\n\n
\uff081\uff09\u9898\u76ee\u63cf\u8ff0<\/strong>\uff1a\u6709 n<\/code> \u4ef6\u7269\u54c1\uff0c\u6bcf\u4ef6\u7269\u54c1\u53ef\u4ee5\u9009\u65e0\u9650\u6b21<\/strong>\uff0c\u6c42\u80cc\u5305\u5bb9\u91cf\u4e3a V<\/code> \u65f6\u7684\u6700\u5927\u4ef7\u503c\u3002<\/p>\n\n\n\n
\uff082\uff09\u6838\u5fc3\u533a\u522b<\/strong>\uff1a\u4e0e 0-1 \u80cc\u5305\u76f8\u6bd4\uff0c\u9009\u4e86\u4e00\u6b21\u7269\u54c1\u540e\u8fd8\u80fd\u7ee7\u7eed\u9009\u8be5\u7269\u54c1\u3002<\/p>\n\n\n\n
\uff083\uff09\u5dee\u5f02\u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n
\u4e00\u3001\n\/\/ 0-1 \u80cc\u5305\ndp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)\n\n\/\/ \u5b8c\u5168\u80cc\u5305\ndp[i][j] = max(dp[i-1][j], dp[i][j-wi] + vi)\n\/\/                  \u2191 \u6ce8\u610f\u8fd9\u91cc\u662f dp[i] \u4e0d\u662f dp[i-1]\n\n\n\u4e8c\u3001\nN, V = map(int, input().split())\ndp = [0] * (V + 1)\n\nfor _ in range(N):\n    w, v = map(int, input().split())\n\n    # \u5173\u952e\uff1a\u5bb9\u91cf j \u6b63\u5e8f\u904d\u5386\n    for j in range(w, V + 1):\n        dp[j] = max(dp[j], dp[j - w] + v)\n\nprint(dp[V])<\/code><\/pre>\n\n\n\n
7\u3001\u591a\u91cd\u80cc\u5305<\/h3>\n\n\n\n
\uff081\uff09\u9898\u76ee\u63cf\u8ff0<\/strong>\uff1a\u6709 n<\/code> \u79cd\u7269\u54c1\uff0c\u7b2c i<\/code> \u79cd\u7269\u54c1\u6700\u591a\u6709 s[i]<\/code> \u4ef6\uff0c\u6bcf\u4ef6\u91cd\u91cf\u4e3a w<\/code>\uff0c\u4ef7\u503c\u4e3a v<\/code>\uff0c\u6c42\u6700\u5927\u4ef7\u503c\u3002<\/p>\n\n\n\n
\uff082\uff09\u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n\nint main() {\n    int N, V;\n    scanf(\"%d %d\", &N, &V);\n\n    \/\/ \u4e8c\u8fdb\u5236\u62c6\u5206\u540e\uff0c\u7269\u54c1\u6570\u91cf\u6700\u591a\u662f N * log(s)\n    int *W = (int *)malloc(sizeof(int) * 200000);\n    int *Val = (int *)malloc(sizeof(int) * 200000);\n    int cnt = 0;  \/\/ \u8bb0\u5f55\u62c6\u5206\u540e\u7269\u54c1\u7684\u771f\u5b9e\u6570\u91cf\n\n    \/\/ \u8bfb\u53d6\u6bcf\u79cd\u7269\u54c1\u5e76\u8fdb\u884c\u4e8c\u8fdb\u5236\u62c6\u5206\n    for (int i = 0; i < N; i++) {\n        int w, v, s;\n        scanf(\"%d %d %d\", &w, &v, &s);\n\n        int k = 1;\n        while (s >= k) {\n            W[cnt] = k * w;\n            Val[cnt] = k * v;\n            cnt++;\n            s -= k;\n            k *= 2\n        }\n\n        \/\/ \u5904\u7406\u5269\u4f59\u90e8\u5206\n        if (s > 0) {\n            W[cnt] = s * w;\n            Val[cnt] = s * v;\n            cnt++;\n        }<\/strong>\n    }\n\n    \/\/ 0-1 \u80cc\u5305 DP \u6570\u7ec4\n    int *dp = (int *)malloc(sizeof(int) * (V + 1));\n    for (int j = 0; j <= V; j++) {\n        dp[j] = 0;\n    }\n\n    \/\/ \u6807\u51c6 0-1 \u80cc\u5305\n    for (int i = 0; i < cnt; i++) {\n        for (int j = V; j >= W[i]; j--) {\n            if (dp[j] < dp[j - W[i]] + Val[i]) {\n                dp[j] = dp[j - W[i]] + Val[i];\n            }\n        }\n    }\n\n    printf(\"%d\\n\", dp[V]);\n\n    \/\/ \u91ca\u653e\u5185\u5b58\n    free(W);\n    free(Val);\n    free(dp);\n\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
1\u3001\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217 \uff081\uff09\u9898\u76ee\u63cf\u8ff0\uff1a\u7ed9\u5b9a\u4e00\u4e2a\u6574\u6570\u6570 …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-84","post","type-post","status-publish","format-standard","hentry","category-7"],"_links":{"self":[{"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/posts\/84","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/comments?post=84"}],"version-history":[{"count":4,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/posts\/84\/revisions"}],"predecessor-version":[{"id":91,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/posts\/84\/revisions\/91"}],"wp:attachment":[{"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/media?parent=84"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/categories?post=84"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/geocommunity.vip\/index.php\/wp-json\/wp\/v2\/tags?post=84"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}