{"id":676,"date":"2025-07-22T02:15:35","date_gmt":"2025-07-21T18:15:35","guid":{"rendered":"http:\/\/47.121.202.229\/?p=676"},"modified":"2025-07-26T03:39:28","modified_gmt":"2025-07-25T19:39:28","slug":"%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%e8%ae%ad%e7%bb%83%e9%98%9f%e9%a2%98%e5%8d%95","status":"publish","type":"post","link":"http:\/\/47.121.202.229\/?p=676","title":{"rendered":"\u52a8\u6001\u89c4\u5212\u8bad\u7ec3\u961f\u9898\u5355"},"content":{"rendered":"\n

Part1 \u7ebf\u6027\u52a8\u6001\u89c4\u5212<\/h2>\n\n\n\n

P2679 [NOIP 2015 \u63d0\u9ad8\u7ec4] \u5b50\u4e32<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n

\u5f88\u6709\u624b\u6cd5\u7684\u4e00\u9053\u52a8\u6001\u89c4\u5212\u3002\u8003\u8651\u7528\u56db\u7ef4dp[i][j][k][v]\u6765\u8fdb\u884c\u52a8\u6001\u89c4\u5212\u3002dp[i][j][k][v]\u8868\u793a\u5f53a\u4e32\u5230\u7b2ci\u4f4d\u65f6\uff0cb\u4e32\u5df2\u7ecf\u5339\u914d\u5230\u4e86\u7b2cj\u4f4d\uff0c\u540c\u65f6\u4f7f\u7528\u4e86k\u4e2a\u5b50\u4e32\uff0c\u5e76\u4e14a[i]\u8fd9\u4e2a\u5b57\u7b26\u662f\u5426\u4f7f\u7528\u4e86\uff08v=0\u8868\u793a\u6ca1\u6709\u7528\uff0c1\u8868\u793a\u7528\u4e86\uff09\u3002\u90a3\u4e48\u5b58\u5728\u4e24\u79cd\u60c5\u51b5\uff1aa[i]==b[j] a[i]!=b[j] \u6bcf\u79cd\u60c5\u51b5\u53c8\u5206\u4f7f\u7528a[i]\u548c\u4e0d\u5b9e\u7528a[i]\u4e24\u79cd\u60c5\u51b5\uff0c\u603b\u5171\u7684\u52a8\u6001\u8f6c\u79fb\u65b9\u7a0b\u5c31\u6709\u56db\u79cd\u60c5\u51b5\uff1a<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

\u4e0b\u9762\u8be6\u7ec6\u89e3\u91ca\u4e00\u4e0b\u4e3a\u4ec0\u4e48\u8981\u8fd9\u6837\u8fdb\u884c\u8f6c\u79fb\uff1a<\/p>\n\n\n\n

\u5f53a[i]==b[j]<\/strong>\u65f6\uff0c\u5982\u679c\u9009\u4e86a[i]<\/strong>\uff0c\u90a3\u4e48\u53ef\u4ee5\u80af\u5b9aa[i-1]\u5339\u914d\u5230\u4e86b[j-1]\u3002\u90a3\u4e48\u5982\u679cdp[i-1][j-1]\u4e5f\u4f7f\u7528\u4e86p\u4e2a\u5b50\u4e32\uff0c\u90a3\u4e48\u53ef\u4ee5\u80af\u5b9aa[i-1]\u548ca[i]\u662f\u8fde\u5728\u4e00\u8d77\u7684\uff0ca[i-1]\u4e5f\u5fc5\u987b\u5f97\u9009\u4e0a\uff0c\u56e0\u6b64\u52a0\u4e0adp[i-1][j-1][p][1]\u3002\u5047\u5982dp[i-1]dp[j-1]\u53ea\u4f7f\u7528\u4e86p-1\u4e2a\u5b50\u4e32\uff0c\u90a3\u4e48\u8fd9\u4e2a\u65f6\u5019\u6709\u4e24\u79cd\u60c5\u51b5\uff0ca[i-1]\u9009\u4e0a\u4e86\u4e0e\u6ca1\u9009\u4e0a\uff0c\u56e0\u6b64\u52a0\u4e0a\u8fd9\u4e24\u79cd\u60c5\u51b5\u3002\u4ece\u524d\u4e00\u4e2a\u72b6\u6001\u8f6c\u79fb\u5230\u540e\u4e00\u4e2a\u72b6\u6001\u65f6\uff0cp\u53ea\u53ef\u80fd+1\u6216\u8005\u4e0d\u52a0\uff0c\u56e0\u6b64\u53ea\u6709p\u548cp-1\u4e24\u79cd\u53ef\u80fd\u3002 \u518d\u770b\u6ca1\u9009a[i]\uff1a<\/strong>\u6ca1\u9009a[i]\u5339\u914d\u5230\u4e86b[j]\uff0c\u90a3\u4e48a[i-1]\u4e5f\u5339\u914d\u5230\u4e86b[j]\u3002\u6ca1\u9009a[i]\u6b64\u65f6\u7528\u4e86p\u4e2a\u5b50\u4e32\uff0c\u90a3\u4e48dp[i-1][j]\u4e5f\u7528\u4e86p\u4e2a\u5b50\u4e32\uff0c\u56e0\u6b64\u53ea\u6709\u4e24\u79cd\u53ef\u80fd\u4e86\uff0ca[i-1]\u4e0eb[j]\u5339\u914d\u4e0a \u548c a[i-1]\u4e0eb[j]\u6ca1\u5339\u914d\u4e0a\uff0c\u56e0\u6b64\u52a0\u4e0a\u8fd9\u4e24\u79cd\u53ef\u80fd\u7684\u60c5\u51b5\u6570\u3002<\/p>\n\n\n\n

\u5982\u679ca[i]!=b[j]<\/strong>\uff0c\u90a3\u4e48a[i]\u5c31\u4e0d\u53ef\u80fd\u88ab\u9009\u4e0a\uff0c\u56e0\u6b64dp[i][j][k][1]=0\uff1b\u5982\u679ca[i]\u6ca1\u9009\u4e0a\uff0c\u548c\u4e0a\u9762\u6ca1\u9009\u4e0a\u7684\u60c5\u51b5\u4e00\u6837\uff0c\u52a0\u4e0a\u8fd9\u4e24\u79cd\u60c5\u51b5\u3002<\/p>\n\n\n\n

\u5f53\u7136\uff0c\u901a\u8fc7\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u53d1\u73b0\uff0c\u6bcf\u4e00\u4e2ai\u53ea\u7528\u5230\u4e86i-1\uff0c\u56e0\u6b64\u53ef\u4ee5\u628ai\u7ed9\u6eda\u52a8\uff0c\u964d\u4f4e\u4e86\u4e00\u5343\u500d\u7a7a\u95f4\u590d\u6742\u5ea6\u3002\u4e0b\u9762\u8d34\u4e0aAC\u4ee3\u7801\uff1a<\/p>\n\n\n\n

#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\nconst int mod = 1000000007;\n\nint n, m, c;\nint dp[2][205][205][2];\nchar a[1005], b[205];\n\nint main() {\n\tios::sync_with_stdio(false);\n\tcin.tie(0);\n\tcin >> n >> m >> c;\n\n\tfor (int i = 1; i <= n; i++) {\n\t\tcin >> a[i];\n\t}\n\tfor (int i = 1; i <= m; i++) {\n\t\tcin >> b[i];\n\t}\n\tint val = 1;\n\tdp[0][0][0][0] = 1;\n\tdp[1][0][0][0] = 1;\n\tfor (int i = 1; i <= n; i++, val ^= 1) {\n\t\tfor (int j = 1; j <= m; j++) {\n\t\t\tfor (int k = 1; k <= c; k++) {\n\t\t\t\tif (a[i] == b[j]) {\n\t\t\t\t\tdp[val][j][k][1] = ((dp[val ^ 1][j - 1][k][1] + dp[val ^ 1][j - 1][k - 1][1]) % mod + dp[val ^ 1][j - 1][k - 1][0]) %\n\t\t\t\t\t                   mod;\n\t\t\t\t\tdp[val][j][k][0] = (dp[val ^ 1][j][k][0] + dp[val ^ 1][j][k][1]) % mod;\n\t\t\t\t} else {\n\t\t\t\t\tdp[val][j][k][1] = 0;\n\t\t\t\t\tdp[val][j][k][0] = (dp[val ^ 1][j][k][0] + dp[val ^ 1][j][k][1]) % mod;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tcout << (dp[n & 1][m][c][1] + dp[n & 1][m][c][0]) % mod;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P1216 [IOI 1994] \u6570\u5b57\u4e09\u89d2\u5f62 Number Triangles<\/h3>\n\n\n\n
\u8fd9\u9898\u6700\u5f00\u59cb\u60f3\u7684\u662f\u7528\u4e00\u7ef4dp\uff0cdp[i]\u8868\u793a\u5230\u7b2ci\u884c\u8def\u5f84\u6700\u5927\u7684\u503c\uff0c\u540e\u9762\u53d1\u73b0\u597d\u50cf\u4e0d\u884c\uff0c\u56e0\u4e3adp[i+1]\u5e76\u4e0d\u662f\u5b8c\u5168\u53d6\u51b3\u4e8edp[i]\uff0c\u8fd8\u8ddf\u524d\u540e\u4e24\u884c\u4f4d\u7f6e\u5173\u7cfb\u6709\u5173\u3002\u56e0\u6b64\u8003\u8651\u4f7f\u7528\u4e8c\u7ef4dp\uff0cdp[i][j]\u8868\u793a\u8d70\u5230\u7b2ci\u884cj\u5217\u7ecf\u8fc7\u6570\u5b57\u6700\u5927\u548c\u3002dp[i][j]\u5c31\u7b49\u4e8edp[i-1][j-1]\u548cdp[i-1][j]\u4e4b\u4e2d\u6700\u5927\u503c\u52a0\u4e0a\u5f53\u524d\u4f4d\u7f6e\u7684\u503c\uff0c\u56e0\u4e3adp[i][j]\u53ea\u80fd\u4ece\u8fd9\u4e24\u4e2a\u4f4d\u7f6e\u6765\u3002\u6700\u540e\u904d\u5386\u4e00\u904ddp\u6570\u7ec4\u7684\u7b2cn\u884c\uff0c\u627e\u5230\u6700\u5927\u503cOK\u4e86\u3002<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\nint arr[1005][1005];\nint n;\nint dp[1005][1005];\n\nint main() {\n\tcin >> n;\n\tfor (int i = 1; i <= n; i++) {\n\t\tfor (int j = 1; j <= i; j++) {\n\t\t\tcin >> arr[i][j];\n\t\t}\n\t}\n\tdp[1][1] = arr[1][1];\n\tfor (int i = 2; i <= n; i++) {\n\t\tfor (int j = 1; j <= i; j++) {\n\t\t\tdp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];\n\t\t}\n\t}\n\tint mx = 0;\n\tfor (int i = 1; i <= n; i++) {\n\t\tmx = max(mx, dp[n][i]);\n\t}\n\tcout << mx;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P1020 [NOIP 1999 \u63d0\u9ad8\u7ec4] \u5bfc\u5f39\u62e6\u622a<\/h3>\n\n\n\n
\u8fd9\u9053\u9898\u5176\u5b9e\u662f\u4e00\u9053\u6700\u957f\u4e0a\u5347\uff08\u4e0d\u964d\uff09\u5b50\u5e8f\u5217\u548c\u6700\u957f\u4e0b\u964d\uff08\u4e0d\u5347\uff09\u5b50\u5e8f\u5217\u7684\u6a21\u7248\u9898\u3002\u4e00\u4e2a\u5e8f\u5217\u4e2d\uff0c\u6700\u957f\u4e0a\u5347\u5b50\u5e8f\u5217\u7684\u957f\u5ea6=\u80fd\u5206\u6210\u7684\u6700\u5c11\u7684\u4e0d\u5347\u5b50\u5e8f\u5217\u7684\u4e2a\u6570\u3002\u7b2c\u4e00\u95ee\u6c42\u6700\u957f\u4e0d\u5347\u5b50\u5e8f\u5217\u957f\u5ea6\uff0c\u7b2c\u4e8c\u95ee\u6c42\u6700\u957f\u4e0a\u5347\u5b50\u5e8f\u5217\u957f\u5ea6\u3002<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nint syb[100005], arr[100005];\nint mx = 0, sz = 0;\n\nvoid getnum() {\n\tint a = 0;\n\tchar c;\n\twhile (c = getchar()) {\n\t\tif (isdigit(c)) {\n\t\t\ta = a * 10 + c - '0';\n\t\t} else if (c == ' ') {\n\t\t\tsz++;\n\t\t\tarr[sz] = a;\n\t\t\ta = 0;\n\t\t} else {\n\t\t\tsz++;\n\t\t\tarr[sz] = a;\n\t\t\tbreak;\n\t\t}\n\t}\n}\n\nint main() {\n\tgetnum();\n\n\tsyb[1] = arr[1];\n\tint msz = 1;\n\tfor (int i = 2; i <= sz; i++) {\n\t\tauto it = upper_bound(syb + 1, syb + 1 + msz, arr[i], greater<int>());\n\t\tif (it == syb + 1 + msz) {\n\t\t\tmsz++;\n\t\t\tsyb[msz] = arr[i];\n\t\t} else {\n\t\t\t*it = arr[i];\n\t\t}\n\t}\n\tcout << msz << endl;\n\tmemset(syb, 0, sizeof(syb));\n\tsyb[1] = arr[1];\n\tmsz = 1;\n\tfor (int i = 2; i <= sz; i++) {\n\t\tauto it = lower_bound(syb + 1, syb + 1 + msz, arr[i]);\n\t\tif (it == syb + 1 + msz) {\n\t\t\tmsz++;\n\t\t\tsyb[msz] = arr[i];\n\t\t} else {\n\t\t\t*it = arr[i];\n\t\t}\n\t}\n\tcout << msz << endl;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P1091 [NOIP 2004 \u63d0\u9ad8\u7ec4] \u5408\u5531\u961f\u5f62<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u5728\u5e8f\u5217\u4e2d\u627e\u5230\u4e00\u4e2a\u4f4d\u7f6ei\uff0c\u4f7f\u5f97\u4ece\u5e8f\u5217\u5f00\u59cb\u5230i\u7684\u4e0a\u5347\u5b50\u5e8f\u5217\u548ci\u5230\u5e8f\u5217\u7ed3\u675f\u7684\u4e0b\u964d\u5b50\u5e8f\u5217\u603b\u7684\u5143\u7d20\u6700\u5927\u3002\u56e0\u6b64\u8fd9\u9053\u9898\u672c\u8d28\u8fd8\u662f\u6c42\u6700\u957f\u4e0a\u5347\u5b50\u5e8f\u5217\uff0c\u6700\u957f\u4e0b\u964d\u5b50\u5e8f\u5217\u3002\u8fd9\u9053\u9898\u6570\u636e\u91cf\u6bd4\u8f83\u5c0f\uff0c\u53ef\u4ee5\u7528O(n*2)\u7684\u65b9\u6cd5\u505a\uff0c\u4f46\u8fd9\u91cc\u8fd8\u662f\u7528O(nlogn)\u7684\u65b9\u6cd5<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\nint left_dp[105], right_dp[105];\nint arr1[105], arr2[105]; \nint d1[105], d2[105]; \n\nint main() {\n    int n;\n    cin >> n;\n    for (int i = 1; i <= n; i++) {\n        cin >> arr1[i];\n        arr2[n - i + 1] = arr1[i]; \n    }\n\n    int len1 = 0;\n    for (int i = 1; i <= n; i++) {\n        auto it = lower_bound(d1 + 1, d1 + 1 + len1, arr1[i]);\n        int pos = it - d1;\n        \n        if (pos > len1) {\n            d1[++len1] = arr1[i];\n            left_dp[i] = len1;\n        } else {\n            *it = arr1[i];\n            left_dp[i] = pos;\n        }\n    }\n\n    int len2 = 0;\n    for (int i = 1; i <= n; i++) {\n        auto it = lower_bound(d2 + 1, d2 + 1 + len2, arr2[i]);\n        int pos = it - d2;\n        \n        if (pos > len2) {\n            d2[++len2] = arr2[i];\n            right_dp[i] = len2;\n        } else {\n            *it = arr2[i];\n            right_dp[i] = pos;\n        }\n    }\n    \/\/ \u5bfb\u627e\u6700\u4f73\u5206\u5272\u70b9\n    int max_len = 0;\n    for (int i = 1; i <= n; i++) {\n        int j = n - i + 1;\n        max_len = max(max_len, left_dp[i] + right_dp[j] - 1);\n    }\n\n    cout << n - max_len << endl;\n    return 0;\n}<\/code><\/pre>\n\n\n\n
P1095 [NOIP 2007 \u666e\u53ca\u7ec4] \u5b88\u671b\u8005\u7684\u9003\u79bb<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u5bf9\u4e8e\u8fd9\u9053\u9898\uff0c\u4f7f\u7528fla\u548crun\u4e24\u4e2a\u53d8\u91cf\u6765\u7ef4\u62a4\u4e24\u79cd\u8ddd\u79bb\u3002\u5982\u679c\u4ee57\u79d2\u949f\u4e3a\u5468\u671f\uff0c\u84c4\u529b\u4e94\u79d2flash\u4e24\u6b21\uff0c\u90a3\u4e48\u80fd\u591f\u8dd1120\u7c73\uff1b\u5355\u7eaf\u8dd17\u79d2\u8dd1119\u7c73\u3002\u56e0\u6b64flash\u6bd4run\u5feb\uff0c\u751a\u81f3\u5f00\u5c40\u8fd8\u6709\u591a\u4f59\u7684\u84dd\u3002\u53d8\u91cffla\u8bb0\u5f55\u7eafflash\u7684\u8ddd\u79bb\uff0crun\u8bb0\u5f55\u7eaf\u8dd1\u7684\u8ddd\u79bb\u3002\u6bcf\u4e00\u79d2\u7ed3\u675f\u540e\uff0c\u5982\u679cfla\u6bd4run\u5927\uff0c\u90a3\u4e48\u628arun\u66f4\u65b0\u4e3afla\u7684\u8ddd\u79bb\u3002\u4e00\u9053\u7b80\u5355\u7684\u52a8\u6001\u89c4\u5212\u3002<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\nint run = 0, fla = 0;\nint m, s, t;\n\n\nint main() {\n\tcin >> m >> s >> t;\n\tfor (int i = 1; i <= t; i++) {\n\t\tif (m >= 10) {\n\t\t\tfla += 60;\n\t\t\trun += 17;\n\t\t\tm -= 10;\n\t\t} else {\n\t\t\tm += 4;\n\t\t\trun += 17;\n\t\t}\n\t\trun = max(run, fla);\n\t\tif (run >= s) {\n\t\t\tcout << \"Yes\" << endl << i;\n\t\t\treturn 0;\n\t\t}\n\t}\n\tcout << \"No\" << endl << run;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P1541 [NOIP 2010 \u63d0\u9ad8\u7ec4] \u4e4c\u9f9f\u68cb<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u8fd9\u9053\u9898\u7b2c\u4e00\u60f3\u6cd5\u5c31\u662f\u628adp[i]\u5f53\u505a\u5230\u7b2ci\u4e2a\u683c\u5b50\u65f6\u6700\u5927\u7684\u5f97\u5206\u6765\u52a8\u6001\u89c4\u5212\uff0c\u4f46\u662f\u8fd9\u6837\u505a\u7684\u8bdd\u5c31\u8981\u8003\u8651\u5230\u8fd9\u4e2a\u683c\u5b50\u662f\u5426\u53ef\u8fbe\uff0c\u8fbe\u5230\u8fd9\u4e2a\u683c\u5b50\u6709\u54ea\u4e9b\u65b9\u6cd5\u90fd\u8981\u8003\u8651\u8fdb\u53bb\uff0c\u5f88\u590d\u6742\u4e0d\u597d\u505a\u3002\u5b9e\u9645\u4e0a\u9898\u76ee\u4e2d\u7ed9\u51fa\u6240\u6709\u7684\u724c\u7528\u5b8c\u4e4b\u540e\u521a\u597d\u80fd\u5230\u8fbe\u7ec8\u70b9\uff0c\u5e76\u4e14\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u5df2\u7ecf\u7528\u6389\u4e86\u54ea\u4e9b\u724c\u6765\u786e\u5b9a\u5f53\u524d\u4f4d\u7f6e\u5728\u54ea\uff0c\u53ef\u4ee5\u7528\u4e00\u4e2a\u56db\u7ef4\u6570\u7ec4\u6765\u52a8\u6001\u89c4\u5212\uff0cdp[a][b][c][d]\u6765\u8868\u793a\u7528\u4e86a\u5f20\u7b2c\u4e00\u79cd\u724c\u3001b\u5f20\u7b2c\u4e8c\u79cd\u724c……\u65f6\u6700\u5927\u7684\u5f97\u5206\uff0c\u53ef\u4ee5\u5f88\u5bb9\u6613\u7684\u77e5\u9053dp[a][b][c][d]\u7531dp[a-1][b][c][d]\u3001dp[a][b-1][c][d]\u3001dp[a][b][c-1][d]\u3001dp[a][b][c][d-1]\u7684\u6700\u5927\u503c\u52a0\u4e0a\u5f53\u524dabcd\u7684\u4f4d\u7f6e\u4e0a\u7684\u5f97\u5206\u800c\u6765\u3002\u6700\u540e\u8f93\u51fadp\u6bcf\u79cd\u724c\u6700\u5927\u6570\u91cf\uff08\u5373\u7ec8\u70b9\uff09\u5c31OK\u4e86<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\nint n, m;\nint arr[355], ka[5];\nint dp[45][45][45][45]; \/\/ \u7ef4\u5ea6\u5927\u5c0f\u6839\u636e\u5361\u7247\u6700\u5927\u6570\u91cf(40)\u8bbe\u7f6e\n\nint main() {\n\tcin >> n >> m;\n\tfor (int i = 1; i <= n; i++) {\n\t\tcin >> arr[i];\n\t}\n\tint temp;\n\tmemset(ka, 0, sizeof(ka)); \/\/ \u521d\u59cb\u5316\u5361\u7247\u8ba1\u6570\n\tfor (int i = 1; i <= m; i++) {\n\t\tcin >> temp;\n\t\tka[temp]++;\n\t}\n\tdp[0][0][0][0] = arr[1];\n\tfor (int a = 0; a <= ka[1]; a++) {\n\t\tfor (int b = 0; b <= ka[2]; b++) {\n\t\t\tfor (int c = 0; c <= ka[3]; c++) {\n\t\t\t\tfor (int d = 0; d <= ka[4]; d++) {\n\t\t\t\t\tint pos = 1 + a + 2 * b + 3 * c + 4 * d;\n\t\t\t\t\tint max_val = -1;\n\t\t\t\t\tif (a > 0)\n\t\t\t\t\t\tmax_val = max(max_val, dp[a - 1][b][c][d]);\n\t\t\t\t\tif (b > 0)\n\t\t\t\t\t\tmax_val = max(max_val, dp[a][b - 1][c][d]);\n\t\t\t\t\tif (c > 0)\n\t\t\t\t\t\tmax_val = max(max_val, dp[a][b][c - 1][d]);\n\t\t\t\t\tif (d > 0)\n\t\t\t\t\t\tmax_val = max(max_val, dp[a][b][c][d - 1]);\n\t\t\t\t\tif (max_val != -1) {\n\t\t\t\t\t\tdp[a][b][c][d] = max_val + arr[pos];\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tcout << dp[ka[1]][ka[2]][ka[3]][ka[4]] << endl;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P1868 \u9965\u997f\u7684\u5976\u725b<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u4e00\u4e2a\u533a\u95f4\u6700\u503c\u95ee\u9898\uff0c\u53ef\u4ee5\u8003\u8651\u7528dp[i]\u6765\u8868\u793a\u5230\u7b2ci\u683c\u65f6\u80fd\u5403\u5230\u7684\u6700\u591a\u7684\u8349\uff0c\u6700\u540e\u7ed3\u679c\u662fdp[\u7ed9\u51fa\u7684\u6700\u53f3\u7aef\u70b9]\u5173\u4e8e\u72b6\u6001\u8f6c\u79fb\uff0c\u5982\u679c\u5f53\u524d\u7684i\u4e0d\u5b58\u5728\u4ee5i\u7ed3\u5c3e\u7684\u533a\u95f4\uff0c\u90a3\u4e48dp[i]=dp[i-1]\uff1b\u5982\u679c\u5b58\u5728\uff0c\u5047\u8bbe\u8fd9\u4e2a\u533a\u95f4\u5de6\u7aef\u70b9\u662fleft\uff0c\u90a3\u4e48\u5c31\u5bf9\u6bd4dp[i-1]\u548cdp[left-1]+\u533a\u95f4\u503c\u3002\u7528\u5927\u503c\u66f4\u65b0dp[i]\u3002<\/p>\n\n\n\n
\u8003\u8651\u7528\u4e00\u4e2apair<int,int>\u6570\u7ec4\u6765\u8bb0\u5f55\u7ed9\u51fa\u7684\u6bcf\u4e2a\u533a\u95f4\uff0c\u7136\u540e\u901a\u8fc7arr[i].second\u7684\u5927\u5c0f\u6765\u5bf9arr\u8fdb\u884csort\u5347\u5e8f\u6392\u5e8f\u3002\u7528mx\u53d8\u91cf\u7ef4\u62a4\u6700\u5927\u7684\u53f3\u7aef\u70b9\uff0c\u521d\u59cb\u5316dp[0]=0\uff0c\u7136\u540e\u5bf9dp[i]\u8fdb\u884c\u4ece1\u5230mx\u7684\u904d\u5386\u3002\u5177\u4f53\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\nint n;\npair<int, int> arr[250005];\nll dp[3000005];\n\nbool cmp(const pair<int, int> &a, const pair<int, int> &b) {\n\treturn a.second < b.second;\n}\n\nint main() {\n\tios::sync_with_stdio(false);\n\tcin.tie(0);\n\tcin >> n;\n\tint mx = 0;\n\tfor (int i = 1; i <= n; i++) {\n\t\tcin >> arr[i].first >> arr[i].second;\n\t\tmx = max(mx, arr[i].second);\n\t}\n\tsort(arr + 1, arr + 1 + n, cmp);\n\tdp[0] = 0;\n\tint sid = 1;\n\n\tfor (int i = 1; i <= mx; i++) {\n\t\tdp[i] = dp[i - 1];\n\t\tif (i != arr[sid].second) {\n\t\t\tcontinue;\n\t\t}\n\t\twhile (i == arr[sid].second && sid <= n) {\n\t\t\tdp[i] = max(dp[i], dp[arr[sid].first - 1] + arr[sid].second - arr[sid].first + 1);\n\t\t\tsid++;\n\t\t}\n\n\t}\n\tcout << dp[mx] << endl;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P3558 [POI 2013] BAJ-Bytecomputer<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u5f88\u725b\u903c\u7684\u4e00\u9053\u52a8\u6001\u89c4\u5212\uff0c\u5b8c\u5168\u7406\u89e3\u8d77\u6765\u4e0d\u662f\u5f88\u5bb9\u6613\u3002\u4ee3\u7801\u501f\u9274\u9898\u89e3\u4e2d\u4e00\u4f4d\u5927\u4f6c\u7684\uff0c\u5f88\u725b\u903c\u7684\u538b\u7f29\uff0c\u5f88\u725b\u903c\u7684\u601d\u8def\uff0c\u5e0c\u671b\u6691\u5047\u7ed3\u675f\u540e\u6211\u4e5f\u80fd\u8fbe\u5230\u8fd9\u6837\u7684\u6c34\u5e73\u3002<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nint n;\nint f[3];\nint inf = 1 << 27;\n\nint main() {\n\tios::sync_with_stdio(false);\n\tcin.tie(0);\n\tcin >> n;\n\tint temp;\n\tcin >> temp;\n\tmemset(f, 63, sizeof(f));\n\tf[temp + 1] = 0;\n\n\tfor (int i = 2; i <= n; i++) {\n\t\tcin >> temp;\n\t\tif (temp == -1) {\n\t\t\tf[1] = inf;\n\t\t\tf[2] += 2;\n\t\t} else if (temp == 0) {\n\t\t\tf[1] = min(f[0], f[1]);\n\t\t\tf[0]++;\n\t\t\tf[2]++;\n\t\t} else {\n\t\t\tf[2] = min(f[0], min(f[1], f[2]));\n\t\t\tf[1] = f[0] + 1;\n\t\t\tf[0] += 2;\n\t\t}\n\t}\n\tint temp1 = min(f[0], min(f[1], f[2]));\n\tif (temp1 >= inf) {\n\t\tcout << \"BRAK\";\n\t} else {\n\t\tcout << temp1;\n\t}\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P4158 [SCOI2009] \u7c89\u5237\u5320<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u7b2c\u4e00\u6b21\u6ca1\u770b\u9898\u89e3\u8fc7\u7684\u84dd\u9898\u3002\u8bb2\u4e00\u4e0b\u6211\u7684\u601d\u8003\u8fc7\u7a0b\u3002\u8fd9\u9053\u9898\u5206\u4e3a\u4e24\u4e2a\u52a8\u6001\u89c4\u5212\u7684\u8fc7\u7a0b\uff0c\u4e5f\u6709\u70b9\u80cc\u5305dp\u7684\u610f\u601d\u3002<\/p>\n\n\n\n
\u72b6\u6001\u8868\u793a\uff1a\u7528dp[i][j]\u6765\u8868\u793a\u524d\u9762i\u884c\u603b\u5171\u7528\u4e86j\u6b21\u673a\u4f1a\u5f97\u5230\u7684\u6700\u5927\u503c\u3002\u90a3\u4e48\u60f3\u5f53\u7136dp[i][j]\u5c31\u7b49\u4e8e  (dp[i-1][j-x]\u52a0\u4e0a\u7b2ci\u884c\u82b1\u8d39x\u6b21\u5f97\u5230\u7684\u6700\u5927\u503c)\u4e2d\u7684\u6700\u5927\u503c\u3002\u56e0\u6b64\u5c31\u5f97\u77e5\u9053\u7b2ci\u884c\u7528x\u6b21\u80fd\u5f97\u5230\u7684\u6700\u5927\u503c\u662f\u591a\u5c11\uff0c\u8fd9\u91cc\u4e5f\u662f\u4e00\u5c42\u52a8\u6001\u89c4\u5212\u3002<\/p>\n\n\n\n
\u5148\u6765\u8bf4\u4e00\u4e0b\u600e\u4e48\u7b2ci\u884c\u7528x\u6b21\u80fd\u5f97\u5230\u7684\u6700\u5927\u503c\u662f\u591a\u5c11\u3002\u9996\u5148\u7528\u4e00\u4e2a\u6570\u7ec4f[i][j][k]\u6765\u8868\u793a\u7b2ci\u884c\u4ecej\u5217\u5230k\u5217\uff0c0\u62161\u603b\u6570\u7684\u8f83\u5927\u503c\uff0c\u5b9e\u9645\u4e0a\u5c31\u662f\u4ecej\u5230k\u53ea\u5237\u4e00\u6b21\u7684\u503c\u3002\u8fd9\u4e2a\u5f88\u597d\u6c42\uff0c\u7528\u66b4\u529b\u5c31\u53ef\u4ee5\u4e86\u3002\u7136\u540e\u7528\u4e00\u4e2a\u6570\u7ec4d[i][j][k]\u7528\u6765\u8868\u793a\u7b2ci\u884c\u524dj\u5217\u7528\u4e86k\u6b21\u673a\u4f1a\u7684\u6700\u5927\u503c\uff0c\u53ef\u4ee5\u77e5\u9053d[i][j][k]=f[i][x][j]+d[i][x-1][k-1]\u7684\u6700\u5927\u503c\u3002\u8fd9\u6837\u4e00\u6765d\u51fd\u6570\u5c31\u6c42\u5b8c\u4e86\u3002<\/p>\n\n\n\n
\u63a5\u4e0b\u6765\u7ed9dp\u6570\u7ec4\u521d\u59cb\u5316\uff0c\u628ad[1][m][x]\u8d4b\u503c\u7ed9\u7ed9dp[i][x]\u3002\u4e4b\u540e\u4ece\u7b2c\u4e8c\u884c\u8fdb\u884cdp\u6570\u7ec4\u7684\u52a8\u6001\u89c4\u5212\u3002\u6700\u540e\u8f93\u51fadp[n][min(t,n*m)]\u5c31\u597d\u4e86\u3002\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nint n, m, t;\nint f[55][55][55];\nint d[55][55][55];\nint dp[55][2505];\nchar arr[55][55];\n\nint main() {\n\tios::sync_with_stdio(false);\n\tcin.tie(0);\n\tcin >> n >> m >> t;\n\tint num = min(m, t);\n\tfor (int i = 1; i <= n; i++) {\n\t\tfor (int j = 1; j <= m; j++) {\n\t\t\tcin >> arr[i][j];\n\t\t}\n\t}\n\tint temp0, temp1;\n\tfor (int i = 1; i <= n; i++) {\n\t\tfor (int j = 1; j <= m; j++) {\n\t\t\ttemp0 = 0, temp1 = 0;\n\t\t\tfor (int k = j; k <= m; k++) {\n\t\t\t\tif (arr[i][k] == '0') {\n\t\t\t\t\ttemp0++;\n\t\t\t\t} else {\n\t\t\t\t\ttemp1++;\n\t\t\t\t}\n\t\t\t\tf[i][j][k] = max(temp0, temp1);\n\t\t\t}\n\t\t}\n\t}\n\n\tfor (int i = 1; i <= n; i++) {\n\n\t\tfor (int j = 1; j <= m; j++) {\n\t\t\td[i][j][1] = f[i][1][j];\n\t\t}\n\n\t\tfor (int k = 2; k <= num; k++) {\n\t\t\tfor (int j = k; j <= m; j++) {\n\t\t\t\tint temp = 0;\n\t\t\t\tfor (int l = j; l >= k; l--) {\n\t\t\t\t\ttemp = max(temp, d[i][l - 1][k - 1] + f[i][l][j]);\n\t\t\t\t}\n\t\t\t\td[i][j][k] = temp;\n\t\t\t}\n\t\t}\n\t}\n\n\tfor (int i = 1; i <= num; i++) {\n\t\tdp[1][i] = d[1][m][i];\n\t}\n\tint temp, mx;\n\tfor (int i = 2; i <= n; i++) {\n\t\tmx = min(t, i * m);\n\t\tfor (int k = 1; k <= mx; k++) {\n\t\t\ttemp = 0;\n\t\t\tfor (int p = 0; p <= min(mx, m); p++) {\n\t\t\t\ttemp = max(temp, d[i][m][p] + dp[i - 1][k - p]);\n\t\t\t}\n\t\t\tdp[i][k] = temp;\n\t\t}\n\t}\n\tmx = min(t, n * m);\n\tcout << dp[n][mx];\n\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P3336 [ZJOI2013] \u8bdd\u65e7<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u6211\u7684\u7b2c\u4e00\u9053\u9ed1\u9898\uff0c\u501f\u9274\u4e86\u5927\u4f6c\u4eec\u7684\u9898\u89e3\u3002\u4ee5\u540e\u4e00\u5b9a\u80fd\u81ea\u5df1\u5199\u51fa\u5f88\u591a\u5f88\u591a\u9053\u9ed1\u9898\uff01<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nconst ll mod = 19940417;\nconst int MAXK = 1000010;\n\nstruct Point {\n\tint x, y;\n};\n\nbool operator<(const Point &a, const Point &b) {\n\treturn a.x < b.x;\n}\n\nbool operator==(const Point &a, const Point &b) {\n\treturn a.x == b.x;\n}\nPoint p[MAXK];\nll f[MAXK][2];\n\nll qpow(ll a, ll b) {\n\tll ret = 1;\n\twhile (b) {\n\t\tif (b % 2)\n\t\t\tret = ret * a % mod;\n\t\tb \/= 2;\n\t\ta = a * a % mod;\n\t}\n\treturn ret;\n}\n\ninline void add(ll &x, ll y) {\n\tx = (x + y % mod) % mod;\n}\n\nint main() {\n\tint n, k, tmax = 0;\n\tscanf(\"%d%d\", &n, &k);\n\tp[k + 1].x = n;\n\tfor (int i = 1; i <= k; i++)\n\t\tscanf(\"%d%d\", &p[i].x, &p[i].y);\n\tsort(p, p + k + 2);\n\tk = unique(p, p + k + 2) - p - 1;\n\tf[0][1] = 1;\n\tfor (int i = 1; i <= k; i++) {\n\t\tint x1 = p[i - 1].x, y1 = p[i - 1].y;\n\t\tint x2 = p[i].x, y2 = p[i].y;\n\t\tint len = x2 - x1 - y1 - y2;\n\t\t\n\t\tif (x1 - x2 == y1 - y2) {\n\t\t\tadd(f[i][0], f[i - 1][0]);\n\t\t\tif (y1 == 0)\n\t\t\t\tadd(f[i][0], f[i - 1][1]);\n\t\t} else if (x1 - x2 == y2 - y1) {\n\t\t\tadd(f[i][1], f[i - 1][0] + f[i - 1][1]);\n\t\t} else if (len < 0) {\n\t\t\tadd(f[i][1], f[i - 1][0]);\n\t\t\tif (y1 == 0)\n\t\t\t\tadd(f[i][1], f[i - 1][1]);\n\t\t} else if (len == 0) {\n\t\t\tadd(f[i][1], f[i - 1][0]);\n\t\t\tif (y1 == 0)\n\t\t\t\tadd(f[i][1], f[i - 1][1]);\n\t\t\tadd(f[i][0], f[i - 1][0] + f[i - 1][1]);\n\t\t} else {\n\t\t\tll t = (2 * f[i - 1][0] + f[i - 1][1]) * qpow(2, len \/ 2 - 1) % mod;\n\t\t\tif (y2 > 0)\n\t\t\t\tadd(f[i][0], t);\n\t\t\tadd(f[i][1], t);\n\t\t}\n\t\tif(f[i][1]>0){\n\t\t\ttmax = max(tmax, x2 - x1 + y1 + y2);\n\t\t}\n\t}\n\tprintf(\"%lld %d\\n\", f[k][1], tmax \/ 2);\n\treturn 0;\n}\n<\/code><\/pre>\n\n\n\n
Part2 \u80cc\u5305\u52a8\u6001\u89c4\u5212<\/h2>\n\n\n\n
P1048 [NOIP 2005 \u666e\u53ca\u7ec4] \u91c7\u836f<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u5b9e\u9645\u4e0a\u5c31\u662f01\u80cc\u5305\u7684\u6a21\u7248\u9898\uff0c\u6362\u4e86\u4e00\u4e2a\u9898\u76ee\u80cc\u666f\u3002\u8fd9\u91cc\u8d34\u4e00\u4e0b\u4e8c\u7ef4dp\u548c\u4e00\u7ef4dp\u7684\u505a\u6cd5<\/p>\n\n\n\n
\u4e8c\u7ef4\uff1a<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nint t, m;\nint dp[105][1005];\npair<int, int> arr[105];\n\nint main() {\n\tcin >> t >> m;\n\tfor (int i = 1; i <= m; i++) {\n\t\tcin >> arr[i].first >> arr[i].second;\n\t}\n\tfor (int i = 1; i <= m; i++) {\n\t\tfor (int j = 1; j <= t; j++) {\n\t\t\tif (j >= arr[i].first) {\n\t\t\t\tdp[i][j] = max(dp[i - 1][j], dp[i - 1][j - arr[i].first] + arr[i].second);\n\t\t\t} else {\n\t\t\t\tdp[i][j] = dp[i - 1][j];\n\t\t\t}\n\n\t\t}\n\t}\n\tcout << dp[m][t] << endl;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\u4e00\u7ef4<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nint t, m;\nint dp[1005];\npair<int, int> arr[105];\n\nint main() {\n\tcin >> t >> m;\n\tfor (int i = 1; i <= m; i++) {\n\t\tcin >> arr[i].first >> arr[i].second;\n\t}\n\tfor (int i = 1; i <= m; i++) {\n\t\tfor (int j = t; j >= 1; j--) {\n\t\t\tif (j >= arr[i].first) {\n\t\t\t\tdp[j] = max(dp[j - arr[i].first] + arr[i].second, dp[j]);\n\t\t\t}\n\n\t\t}\n\t}\n\tcout << dp[t] << endl;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P1060 [NOIP 2006 \u666e\u53ca\u7ec4] \u5f00\u5fc3\u7684\u91d1\u660e
<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u8fd8\u662f\u4e00\u905301\u80cc\u5305\uff0c\u552f\u4e00\u7684\u53d8\u5316\u662f\u8981\u5bf9\u7269\u54c1\u7684\u4ef7\u503c\u505a\u4e00\u4e0b\u5904\u7406<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nint n, m;\nint dp[30005];\npair<int, int> arr[30];\n\nint main() {\n\tcin >> n >> m;\n\tint temp;\n\tfor (int i = 1; i <= m; i++) {\n\t\tcin >> arr[i].first >> temp;\n\t\tarr[i].second = temp * arr[i].first;\n\t}\n\tfor (int i = 1; i <= m; i++) {\n\t\tfor (int j = n; j >= 0; j--) {\n\t\t\tif (j >= arr[i].first) {\n\t\t\t\tdp[j] = max(dp[j], dp[j - arr[i].first] + arr[i].second);\n\t\t\t}\n\t\t}\n\t}\n\tcout << dp[n];\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P1855 \u69a8\u53d6kkksc03<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u4ece01\u80cc\u5305\uff08\u53ea\u6709\u4e00\u4e2a\u80cc\u5305\uff0c\u5373\u53ea\u6709\u4e00\u79cd\u8d44\u672c\uff09\u53d8\u6210\u4e86\u591a\u7ef4\u80cc\u5305\uff0c\u8fd9\u9898\u662f\u4e8c\u7ef4\u80cc\u5305\uff0c\u62e5\u6709\u4e24\u4e2a\u80cc\u5305\u3002<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nint n, m, t;\nint dp[205][205];\npair<int, int> arr[105];\n\nint main() {\n\tcin >> n >> m >> t;\n\tfor (int i = 1; i <= n; i++) {\n\t\tcin >> arr[i].first >> arr[i].second;\n\t}\n\tfor (int i = 1; i <= n; i++) {\n\t\tfor (int j = m; j >= 0; j--) {\n\t\t\tfor (int k = t; k >= 0; k--) {\n\t\t\t\tif (j >= arr[i].first && k >= arr[i].second) {\n\t\t\t\t\tdp[j][k] = max(dp[j][k], dp[j - arr[i].first][k - arr[i].second] + 1);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tcout << dp[m][t];\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P5020 [NOIP 2018 \u63d0\u9ad8\u7ec4] \u8d27\u5e01\u7cfb\u7edf<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u4e00\u9053\u5b8c\u5168\u80cc\u5305\u7684\u9898\u3002\u5c06\u539f\u6765\u96c6\u5408\u4e2d\u6240\u6709\u80fd\u88ab\u5176\u5b83\u6570\u5b57\u7ec4\u6210\u7684\u6570\u90fd\u5220\u53bb\uff0c\u5269\u4e0b\u5143\u7d20\u7684\u4e2a\u6570\u5c31\u662f\u8981\u8f93\u51fa\u7684\u503c\u3002\u56e0\u6b64\u5bf9\u9762\u503c\u8fdb\u884c\u6392\u5e8f\uff0c\u4ece\u6700\u5c0f\u7684\u9762\u503c\u5f00\u59cb\u904d\u5386\uff0c\u5e76\u4e14\u904d\u5386\u5f53\u524d\u9762\u503c\u540e\u9762\u7684\u6240\u6709\u503c\u8fdb\u884c\u51d1\u503c\u3002AC\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nconst int maxdp = 25005;\nconst int maxn = 105;\nint n, t, ans;\nint f[maxdp];\nint a[maxn];\n\nint main() {\n\tscanf(\"%d\", &t);\n\twhile (t--) {\n\t\tmemset(f, 0, sizeof(f));\n\t\tscanf(\"%d\", &n);\n\t\tans = n;\n\t\tfor (int i = 1; i <= n; i++) {\n\t\t\tscanf(\"%d\", &a[i]);\n\t\t}\n\t\tsort(a + 1, a + n + 1);\n\t\tf[0] = 1;\n\t\tfor (int i = 1; i <= n; i++) {\n\t\t\tif (f[a[i]]) {\n\t\t\t\tans--;\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tfor (int j = a[i]; j <= a[n]; j++) {\n\t\t\t\tf[j] = f[j] | f[j - a[i]];\n\t\t\t}\n\t\t}\n\t\tprintf(\"%d\\n\", ans);\n\t}\n\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P1757 \u901a\u5929\u4e4b\u5206\u7ec4\u80cc\u5305<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u5982\u9898\u540d\uff0c\u5206\u7ec4\u80cc\u5305\u7684\u677f\u5b50\u9898\u3002\u6bd4\u8f83\u590d\u6742\u7684\u70b9\u5728\u4e8e\u8bb0\u5f55\u5206\u7ec4\u4e0e\u6bcf\u4e2a\u5206\u7ec4\u7269\u54c1\u5bf9\u5e94\u7684\u7f16\u53f7<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nint n, m;\nint w[1005], v[1005], b[1005], g[1005][1005], dp[1005];\n\nint main() {\n\tcin >> m >> n;\n\tint temp;\n\tint t = 0;\n\tfor (int i = 1; i <= n; i++) {\n\t\tcin >> w[i] >> v[i] >> temp;\n\t\tt = max(t, temp);\n\t\tb[temp]++;\n\t\tg[temp][b[temp]] = i;\n\t}\n\tfor (int i = 1; i <= t; i++) {\n\t\tfor (int j = m; j >= 0; j--) {\n\t\t\tfor (int k = 1; k <= b[i]; k++) {\n\t\t\t\tif (j >= w[g[i][k]]) {\n\t\t\t\t\tdp[j] = max(dp[j], dp[j - w[g[i][k]]] + v[g[i][k]]);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tcout << dp[m];\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P1064 [NOIP 2006 \u63d0\u9ad8\u7ec4] \u91d1\u660e\u7684\u9884\u7b97\u65b9\u6848<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u6bcf\u4e00\u7ec4\u7269\u54c1\u5fc5\u987b\u9009\u62e9\u4e3b\u9879\uff0c\u624d\u80fd\u518d\u9009\u62e9\u526f\u9879\uff0c\u56e0\u6b64\u5bf9\u4e8e\u6bcf\u4e00\u7ec4\u7269\u54c1\uff0c\u603b\u5171\u6709\u4e94\u79cd\u9009\u62e9\u60c5\u51b5\uff1a1.\u4e0d\u9009\u62e9\u8be5\u7ec42.\u9009\u62e9\u4e3b\u98793.\u9009\u62e9\u4e3b\u9879\u548c\u7b2c\u4e00\u4e2a\u526f\u98794.\u9009\u62e9\u4e3b\u9879\u548c\u7b2c\u4e8c\u4e2a\u526f\u98795.\u9009\u62e9\u4e3b\u9879\u548c\u4e24\u4e2a\u526f\u9879\u3002\u6309\u7167\u6bcf\u4e00\u7ec4\u8fdb\u884c\u80cc\u5305dp<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nint n, m;\nint w[65][3], v[65][3], b[65], dp[30005];\n\nint main() {\n\tcin >> n >> m;\n\tint temp1, temp2, temp3;\n\tfor (int i = 1; i <= m; i++) {\n\t\tcin >> temp1 >> temp2 >> temp3;\n\t\tif (temp3 == 0) {\n\t\t\tb[i] = 1;\n\t\t\tw[i][0] = temp1;\n\t\t\tv[i][0] = temp2;\n\t\t} else {\n\t\t\tif (w[temp3][1] == 0) {\n\t\t\t\tw[temp3][1] = temp1;\n\t\t\t\tv[temp3][1] = temp2;\n\t\t\t} else {\n\t\t\t\tw[temp3][2] = temp1;\n\t\t\t\tv[temp3][2] = temp2;\n\t\t\t}\n\t\t}\n\t}\n\n\tfor (int i = 1; i <= m; i++) {\n\t\tif (!b[i]) {\n\t\t\tcontinue;\n\t\t}\n\t\tfor (int j = n; j >= 0; j--) {\n\t\t\tif (j >= w[i][0] + w[i][1] + w[i][2]) {\n\t\t\t\tdp[j] = max(dp[j], dp[j - w[i][0] - w[i][1] - w[i][2]] + w[i][0] * v[i][0] + w[i][1] * v[i][1] + w[i][2] * v[i][2]);\n\t\t\t}\n\t\t\tif (j >= w[i][0] + w[i][1]) {\n\t\t\t\tdp[j] = max(dp[j], dp[j - w[i][0] - w[i][1]] + w[i][0] * v[i][0] + w[i][1] * v[i][1]);\n\t\t\t}\n\t\t\tif (j >= w[i][0] + w[i][2]) {\n\t\t\t\tdp[j] = max(dp[j], dp[j - w[i][0] - w[i][2]] + w[i][0] * v[i][0] + w[i][2] * v[i][2]);\n\t\t\t}\n\t\t\tif (j >= w[i][0]) {\n\t\t\t\tdp[j] = max(dp[j], dp[j - w[i][0]] + w[i][0] * v[i][0]);\n\t\t\t}\n\t\t}\n\t}\n\tcout << dp[n];\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P2946 [USACO09MAR] Cow Frisbee Team S<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u9898\u76ee\u6807\u7b7e\u662f\u80cc\u5305dp\uff0c\u867d\u7136\u8bf4\u80cc\u5305dp\u4e5f\u662f\u7ebf\u6027dp\u7684\u4e00\u79cd\uff0c\u4f46\u6211\u611f\u89c9\u66f4\u50cf\u6807\u51c6\u7684\u7ebf\u6027dp\u3002<\/p>\n\n\n\n
\u72b6\u6001\u8868\u793a\uff1a\u7528dp[i][j]\u6765\u8868\u793a\u524di\u4e2a\u5976\u725b\u4e2d\u4ee5j\u4e3a\u4f59\u6570\u7684\u603b\u7ec4\u5408\u6570\u3002\u5047\u8bbe\u5f53\u524d\u7b2ci\u4e2a\u5976\u725b\u7684\u80fd\u529b\u503c\u662fx\uff0c\u90a3\u4e48\u60f3\u8981\u6c42\u5230\u7b2ci\u4e2a\u5976\u725b\u7684\u65f6\u5019\u4f59\u6570\u4e3aj\u7684\u7ec4\u5408\u6570\uff0c\u5c31\u8981\u77e5\u9053\u524d\u9762i-1\u4e2a\u5976\u725b\u4f59\u6570\u662f (j+f-x)%f  \u7684\u7ec4\u5408\u6570\u3002\u7279\u522b\u7684\uff0c\u5f53\u524d\u5976\u725b\u80fd\u529b\u503c\u5c31\u662fj\u65f6\uff0c\u8fd8\u8981\u518d\u52a01\uff0c\u56e0\u4e3a\u672c\u8eab\u4e5f\u662f\u4e00\u4e2a\u7ec4\u5408\u3002<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nconst int mod = 1e8;\nint n, f;\nint arr[2005];\nint dp[2005][1005];\n\nint main() {\n\tcin >> n >> f;\n\tint temp;\n\tfor (int i = 1; i <= n; i++) {\n\t\tcin >> temp;\n\t\tarr[i] = temp % f;\n\t}\n\n\n\tfor (int i = 1; i <= n; i++) {\n\t\tdp[i][arr[i]] += 1;\n\t\tfor (int j = 0; j < f; j++) {\n\t\t\tdp[i][j] += (dp[i - 1][(j + f - arr[i]) % f] + dp[i - 1][j]) % mod ;\n\t\t}\n\n\t}\n\tcout << dp[n][0];\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P5322 [BJOI2019] \u6392\u5175\u5e03\u9635<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u6bcf\u4e2a\u57ce\u5821\u662f\u4e00\u4e2a\u7269\u54c1\uff0c\u58eb\u5175\u6570\u662f\u80cc\u5305\u5bb9\u91cf\uff0c\u548c01\u80cc\u5305\u4e0d\u540c\u7684\u662f\uff0c01\u80cc\u5305\u76f4\u63a5\u51cf\u53bb\u5bb9\u91cf\u6362\u53d6\u5f97\u5206\uff0c\u4f46\u662f\u8fd9\u9053\u9898\u662f\u5206\u914d\u4e0d\u540c\u7684\u5bb9\u91cf\uff0c\u62ff\u5230\u4e0d\u540c\u7684\u5f97\u5206\uff0c\u56e0\u6b64\u8fd9\u9898\u9700\u8981\u518d\u52a0\u4e00\u4e2a\u5185\u5c42\u5faa\u73af\u53bb\u904d\u5386\u5bb9\u91cf\u7684\u53d6\u503c\uff0c\u800c\u5bb9\u91cf\u7684\u53d6\u503c\u53d6\u51b3\u4e8e\u5f53\u524d\u57ce\u5821\u6bcf\u4e2a\u5176\u4ed6\u73a9\u5bb6\u6d3e\u9063\u7684\u6570\u76ee\uff0c\u6839\u636e\u8fd9\u4e2a\u6765\u786e\u5b9a\u3002AC\u4ee3\u7801\u5982\u4e0b<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nint s, n, m;\nint  dp[20005], tar[105][105];\n\nint main() {\n\tcin >> s >> n >> m;\n\n\tfor (int i = 1; i <= s; i++) {\n\t\tfor (int j = 1; j <= n; j++) {\n\t\t\tcin >> tar[j][i];\n\t\t}\n\t}\n\tfor (int i = 1; i <= n; i++) {\n\t\tsort(tar[i] + 1, tar[i] + 1 + s);\n\t}\n\n\tint temp;\n\tfor (int i = 1; i <= n; i++) {\n\t\tfor (int j = m; j >= 0; j--) {\n\t\t\tfor (int k = 1; k <= s; k++) {\n\t\t\t\ttemp = tar[i][k] * 2 + 1;\n\t\t\t\tif (j >= temp) {\n\t\t\t\t\tdp[j] = max(dp[j], dp[j - temp] + k * i);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tcout << dp[m];\n\treturn 0;\n}\n<\/code><\/pre>\n\n\n\n
P1156 \u5783\u573e\u9677\u9631<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nint dis, n;\n\nstruct rbs {\n\tint t;\n\tint h;\n\tint f;\n} rb[110]; \nint f[110], ti[110];\n\nbool cmp(rbs a, rbs b) {\n\treturn a.t < b.t;\n}\n\nint main() {\n\tcin >> dis >> n;\n\tfor (int i = 1; i <= n; i++) {\n\t\tcin >> rb[i].t >> rb[i].f >> rb[i].h;\n\t}\n\tsort(rb + 1, rb + 1 + n, cmp);\n\tf[0] = 10;\n\tfor (int i = 1; i <= n; i++) {\n\t\tfor (int j = dis; j >= 0; j--) {\n\t\t\tif (f[j] >= rb[i].t) {\n\t\t\t\tif (j + rb[i].h >= dis) {\n\t\t\t\t\tcout << rb[i].t << endl; \n\t\t\t\t\treturn 0;\n\t\t\t\t}\n\t\t\t\tf[j + rb[i].h] = max(f[j + rb[i].h], f[j]);\n\t\t\t\tf[j] += rb[i].f;\n\t\t\t}\n\t\t}\n\t}\n\tcout << f[0] << endl; \n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
Part3 \u533a\u95f4\u52a8\u6001\u89c4\u5212<\/h2>\n\n\n\n
\u533a\u95f4\u52a8\u6001\u89c4\u5212\uff0c\u5c31\u662f\u4ee5\u533a\u95f4\u4f5c\u4e3a\u52a8\u6001\u89c4\u5212\u7684\u9636\u6bb5\u3002<\/p>\n\n\n\n
P1880 [NOI1995] \u77f3\u5b50\u5408\u5e76<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\nconst int INF = 1e9;\nint n, arr[205], sum[205], dpm[205][205], dpx[205][205];\n\nint main() {\n\tcin >> n;\n\tfor (int i = 1; i <= n; i++) {\n\t\tcin >> arr[i];\n\t\tarr[i + n] = arr[i]; \/\/ \u73af\u5f62\u5c55\u5f00\n\t}\n\tfor (int i = 1; i <= 2 * n; i++)\n\t\tsum[i] = sum[i - 1] + arr[i]; \/\/ \u6b63\u786e\u8ba1\u7b97\u524d\u7f00\u548c\n\n\t\/\/ \u521d\u59cb\u5316DP\n\tfor (int len = 1; len <= n; len++) {\n\t\tfor (int i = 1; i + len - 1 <= 2 * n; i++) {\n\t\t\tint j = i + len - 1;\n\t\t\tif (len == 1) {\n\t\t\t\tdpm[i][j] = 0;\n\t\t\t\tdpx[i][j] = 0;\n\t\t\t} else {\n\t\t\t\tdpm[i][j] = INF;\n\t\t\t\tdpx[i][j] = -INF;\n\t\t\t\tfor (int k = i; k < j; k++) {\n\t\t\t\t\tdpm[i][j] = min(dpm[i][j], dpm[i][k] + dpm[k + 1][j] + sum[j] - sum[i - 1]);\n\t\t\t\t\tdpx[i][j] = max(dpx[i][j], dpx[i][k] + dpx[k + 1][j] + sum[j] - sum[i - 1]);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\n\t\/\/ \u904d\u5386\u6240\u6709\u8d77\u70b9\u53d6\u6700\u4f18\u89e3\n\tint min_ans = INF, max_ans = -INF;\n\tfor (int i = 1; i <= n; i++) {\n\t\tmin_ans = min(min_ans, dpm[i][i + n - 1]);\n\t\tmax_ans = max(max_ans, dpx[i][i + n - 1]);\n\t}\n\tcout << min_ans << endl << max_ans;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P3146 [USACO16OPEN] 248 G<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\nint n;\nint arr[255], dp[255][255],ans=0;\n\nint main() {\n\tcin >> n ;\n\tfor (int i = 1; i <= n; i++) {\n\t\tcin >> arr[i];\n\t}\n\tfor (int k = 1; k <= n; k++) {\n\t\tfor (int i = 1; i + k - 1 <= n; i++) {\n\t\t\tif (k == 1) {\n\t\t\t\tdp[i][i + k - 1] = arr[i];\n\t\t\t\tans=max(ans,arr[i]);\n\t\t\t} else {\n\t\t\t\tfor (int j = i; j < i + k - 1; j++) {\n\t\t\t\t\tif (dp[i][j] == dp[j+1][i + k - 1]&&dp[i][j]) {\n\t\t\t\t\t\tdp[i][i + k - 1] = max(dp[i][i + k - 1], dp[i][j] + 1);\n\t\t\t\t\t\tans=max(ans,dp[i][i+k-1]);\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tcout << ans;\n\treturn 0;\n}\n<\/code><\/pre>\n\n\n\n
P1063 [NOIP 2006 \u63d0\u9ad8\u7ec4] \u80fd\u91cf\u9879\u94fe<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u9996\u5148\u662f\u4e00\u9053\u73af\u5f62\u7684\u9898\uff0c\u56e0\u6b64\u5bf9\u73af\u5f62\u8fdb\u884c\u5904\u7406\uff0c\u5728\u539f\u6570\u636e\u6570\u7ec4\u57fa\u7840\u4e0a\u590d\u5236\u4e00\u4efd\uff0c\u52a8\u6001\u89c4\u5212\u7684\u65f6\u5019\u90fd\u8981\u4e00\u8d77\u66f4\u65b0\uff0c\u6700\u540e\u4ece1\u5230n\u8fdb\u884c\u957f\u5ea6\u4e3an\u7684\u904d\u5386\uff0c\u627e\u5230\u6700\u5927\u503c\u3002<\/p>\n\n\n\n
\u7528pair<int,int> arr\u6570\u7ec4\u8bb0\u5f55\u6bcf\u4e2a\u6570\u636e\u7684\u5934\u548c\u5c3e\u3002\u52a8\u6001\u89c4\u5212\u65f6\uff0c\u904d\u5386j\uff0c\u627e\u5230 i\u5230i+len-1\u7684\u6700\u5927\u503c\uff1ai\u5230j\u7684\u6700\u5927\u503c\u52a0\u4e0aj+1\u5230i+len-1\u7684\u6700\u5927\u503c\u52a0\u4e0a\u4e09\u4e2a\u6570\u76f8\u4e58 \u7684\u6700\u5927\u503c\u3002AC\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\nint n;\npair<int, int> arr[205];\nint dp[205][205];\n\nint main() {\n\tcin >> n;\n\tfor (int i = 1; i <= n; i++) {\n\t\tif (i == 1) {\n\t\t\tcin >> arr[i].first >> arr[i].second;\n\t\t} else if (i == n) {\n\t\t\tarr[i].first = arr[i - 1].second;\n\t\t\tarr[i].second = arr[1].first;\n\t\t} else {\n\t\t\tcin >> arr[i].second;\n\t\t\tarr[i].first = arr[i - 1].second;\n\t\t}\n\t\tarr[i + n].first = arr[i].first;\n\t\tarr[i + n].second = arr[i].second;\n\n\t}\n\tfor (int i = 1; i <= 2 * n; i++) {\n\t\tdp[i][i] = 0;\n\t}\n\tfor (int len = 2; len <= n; len++) {\n\t\tfor (int i = 1; i + len - 1 <= 2 * n; i++) {\n\t\t\tfor (int j = i; j < i + len - 1; j++) {\n\t\t\t\tdp[i][i + len - 1] = max(dp[i][i + len - 1],\n\t\t\t\t                         dp[i][j] + dp[j + 1][i + len - 1] + arr[i].first * arr[j].second * arr[i + len - 1].second);\n\t\t\t}\n\t\t}\n\t}\n\tint ans = 0;\n\tfor (int i = 1; i <= n; i++) {\n\t\tans = max(ans, dp[i][i + n - 1]);\n\t}\n\tcout << ans;\n\treturn 0;\n}\n\n<\/code><\/pre>\n\n\n\n
P1005 [NOIP 2007 \u63d0\u9ad8\u7ec4] \u77e9\u9635\u53d6\u6570\u6e38\u620f<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u5b66\u4e86\u4e00\u624b__int128 \u7684\u7528\u6cd5<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nint n, m;\nint arr[85];\n__int128 dp[85][85], ans;\n\nvoid out (__int128 x) {\n\tif (x > 9)\n\t\tout(x \/ 10);\n\tputchar(x % 10 + '0');\n}\n\nint main() {\n\tcin >> n >> m;\n\tint t = n;\n\twhile (t--) {\n\t\tmemset(dp, 0, sizeof(dp));\n\t\tfor (int i = 1; i <= m; i++) {\n\t\t\tcin >> arr[i];\n\t\t\tdp[i][i] = 2 * arr[i];\n\t\t}\n\t\tfor (int len = 2; len <= m; len++) {\n\t\t\tfor (int i = 1; i + len - 1 <= m; i++) {\n\t\t\t\tint j = i + len - 1;\n\t\t\t\tfor (int k = i; k < j; k++) {\n\t\t\t\t\tdp[i][j] = max(dp[i + 1][j] + arr[i], dp[i][j - 1] + arr[j]) * 2;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\tans += dp[1][m];\n\t}\n\tout(ans);\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P4170 [CQOI2007] \u6d82\u8272<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long;\n\nstring s;\nchar tar[55];\nint dp[55][55], ans;\n\nint main() {\n\tcin >> s;\n\tint sz = s.size();\n\tfor (int i = 1; i <= sz; i++) {\n\t\tdp[i][i] = 1;\n\t\ttar[i] = s[i - 1];\n\t}\n\n\tfor (int len = 2; len <= sz; len++) {\n\t\tfor (int i = 1; i + len - 1 <= sz; i++) {\n\t\t\tint j = i + len - 1;\n\t\t\tif (tar[i] == tar[j]) {\n\t\t\t\tdp[i][j] = dp[i][j - 1];\n\t\t\t} else {\n\t\t\t\tdp[i][j] = dp[i][i] + dp[i + 1][j];\n\t\t\t\tfor (int k = i; k < j; k++) {\n\t\t\t\t\tdp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tcout << dp[1][sz];\n\treturn 0;\n}\n<\/code><\/pre>\n\n\n\n
P4302 [SCOI2003] \u5b57\u7b26\u4e32\u6298\u53e0<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nstring st;\nint n, m[110], f[110][110];\n\nbool check(int l, int r, int len) {\n\tfor (int i = l; i <= r; i++)\n\t\tif (st[i] != st[(i - l) % len + l])\n\t\t\treturn false;\n\treturn true;\n}\n\nint main() {\n\tcin >> st;\n\tn = st.size();\n\tst = ' ' + st;\n\tfor (int i = 1; i <= 9; i++)\n\t\tm[i] = 1;\n\tfor (int i = 10; i <= 99; i++)\n\t\tm[i] = 2;\n\tm[100] = 3;\n\tmemset(f, 0x3f, sizeof(f));\n\tfor (int i = 1; i <= n; i++)\n\t\tf[i][i] = 1;\n\tfor (int l = 2; l <= n; l++) {\n\t\tfor (int i = 1, j = i + l - 1; j <= n; i++, j++) {\n\t\t\tfor (int k = i; k < j; k++)\n\t\t\t\tf[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);\n\t\t\tfor (int k = i; k < j; k++) {\n\t\t\t\tint len = k - i + 1;\n\t\t\t\tif (l % len != 0)\n\t\t\t\t\tcontinue;\n\t\t\t\tif (check(i, j, len))\n\t\t\t\t\tf[i][j] = min(f[i][j], f[i][k] + 2 + m[l \/ len]);\n\t\t\t}\n\t\t}\n\t}\n\tprintf(\"%d\", f[1][n]);\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P2466 [SDOI2008] Sue \u7684\u5c0f\u7403<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u7b80\u5355\u8bb2\u4e00\u4e0b\u6211\u7684\u601d\u8003\u8fc7\u7a0b\uff1a\u8fd9\u8fd8\u662f\u4e00\u9053\u533a\u95f4dp\uff0c\u6700\u5f00\u59cb\u60f3\u7684\u662f\u8ba9dp[i][j]\u8868\u793a\u7b2ci\u4e2a\u5230\u7b2cj\u4e2a\u533a\u95f4\u5f97\u5206\u6700\u5927\u503c\u3002\u4f46\u662f\uff0c\u600e\u4e48\u5408\u5e76\u533a\u95f4\u5462\uff0c\u6216\u8005\u8bf4\u600e\u4e48\u63a8\u5230\u4e0b\u4e00\u4e2a\u533a\u95f4\u5462\uff1f\u53d1\u73b0\u597d\u50cf\u6ca1\u6709\u5f88\u597d\u7684\u529e\u6cd5\uff0c\u56e0\u4e3a\u5e76\u4e0d\u77e5\u9053\u662f\u4ece\u4ec0\u4e48\u65f6\u5019\u5230\u8fd9\u4e2a\u533a\u95f4\u7684\uff0c\u4e0d\u77e5\u9053\u6b64\u65f6\u7684\u65f6\u95f4\uff0c\u81ea\u7136\u5c31\u65e0\u6cd5\u77e5\u9053\u5f97\u5206\u3002<\/p>\n\n\n\n
\u53ef\u4ee5\u8003\u8651\u7528dp[i][j]\u8868\u793a\u4ecei\u5230j\u8fd9\u4e2a\u533a\u95f4\u7684\u8fc7\u7a0b\u4e2d\uff0c\u5176\u5b83\u533a\u95f4\u6700\u5c11\u4f1a\u6d6a\u8d39\u591a\u5c11\u79ef\u5206\u3002f[i][j]\u8868\u793a\u5f53\u5904\u4e8ei\u70b9\u65f6\uff0c\u7ecf\u8fc7\u4e86i\u5230j\u6d6a\u8d39\u7684\u6700\u5c11\u79ef\u5206\uff1bg[i][j]\u8868\u793a\u5904\u4e8ej\u70b9\u65f6\u6d6a\u8d39\u7684\u79ef\u5206\u3002\u521d\u59cb\u4f4d\u7f6e\u4e3ax\uff0c\u5219f[x][x]=g[x][x]=0\u3002<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n#define MAXN 1005\n#define rg register\nstruct zjy{\n    int x,y,v;\n}ball[MAXN];\nint f[MAXN][MAXN],g[MAXN][MAXN],tot;\nint x0,n,pre[MAXN];\nbool cmp(zjy x,zjy y){return x.x<y.x;}\nint js(int l,int r){return pre[r]-pre[l-1];}\nint main(){\n    memset(f,0x3f,sizeof(f));\n    memset(g,0x3f,sizeof(g));\n    ios::sync_with_stdio(false);\n    cin>>n>>x0;\n    for(rg int i=1;i<=n;++i)cin>>ball[i].x;\n    for(rg int i=1;i<=n;++i)cin>>ball[i].y,tot+=ball[i].y;\n    for(rg int i=1;i<=n;++i)cin>>ball[i].v;\n    ball[++n].x=x0;\n    sort(ball+1,ball+n+1,cmp);\n    for(rg int i=1;i<=n;++i)pre[i]=pre[i-1]+ball[i].v;\n    for(rg int i=1;i<=n;++i)if(ball[i].v==0&&ball[i].x==x0)f[i][i]=0,g[i][i]=0;\n    for(rg int k=1;k<n;++k)for(rg int i=1,j=i+k;i<=n&&j<=n;++i,j=i+k){\n        f[i][j]=min(f[i][j],f[i+1][j]+(js(1,i)+js(j+1,n))*(ball[i+1].x-ball[i].x));\n        f[i][j]=min(f[i][j],g[i+1][j]+(js(1,i)+js(j+1,n))*(ball[j].x-ball[i].x));\n        g[i][j]=min(g[i][j],g[i][j-1]+(js(1,i-1)+js(j,n))*(ball[j].x-ball[j-1].x));\n        g[i][j]=min(g[i][j],f[i][j-1]+(js(1,i-1)+js(j,n))*(ball[j].x-ball[i].x));\n    }\n    printf(\"%.3lf\",(tot-min(f[1][n],g[1][n]))\/1000.0);\n}<\/code><\/pre>\n\n\n\n
Part4 \u6811\u5f62\u52a8\u6001\u89c4\u5212<\/h2>\n\n\n\n
\u6811\u5f62\u52a8\u6001\u89c4\u5212\uff0c\u5373\u5728\u6811\u4e0a\u8fdb\u884c\u7684\u52a8\u6001\u89c4\u5212\u3002\u56e0\u4e3a\u6811\u7684\u9012\u5f52\u6027\u8d28\uff0c\u6811\u5f62\u52a8\u6001\u89c4\u5212\u4e00\u822c\u90fd\u662f\u9012\u5f52\u6c42\u89e3\u7684\u3002<\/p>\n\n\n\n
P1352 \u6ca1\u6709\u4e0a\u53f8\u7684\u821e\u4f1a<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u4e00\u9053\u7ecf\u5178\u7684\u6811\u5f62dp\u3002<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\nint n, v[6005], syb[6005], root, dp[6005][2];\nvector<int> son[6005];\n\nvoid dfs(int x) {\n\tdp[x][0] = 0;\n\tdp[x][1] = v[x];\n\tfor (int i = 0; i < son[x].size(); i++) {\n\t\tint tar = son[x][i];\n\t\tdfs(tar);\n\t\tdp[x][0] += max(dp[tar][0], dp[tar][1]);\n\t\tdp[x][1] += dp[tar][0];\n\t}\n\treturn;\n}\n\nint main() {\n\tcin >> n;\n\tfor (int i = 1; i <= n; i++) {\n\t\tcin >> v[i];\n\t}\n\tint temp1, temp2;\n\tfor (int i = 1; i <= n - 1; i++) {\n\t\tcin >> temp1 >> temp2;\n\t\tson[temp2].push_back(temp1);\n\t\tsyb[temp1] = 1;\n\t}\n\tfor (int i = 1; i <= n; i++) {\n\t\tif (!syb[i]) {\n\t\t\troot = i;\n\t\t\tbreak;\n\t\t}\n\t}\n\tdfs(root);\n\tcout << max(dp[root][0], dp[root][1]);\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P1122 \u6700\u5927\u5b50\u6811\u548c<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u9898\u76ee\u80cc\u666f\u7684\u610f\u601d\uff0c\u5176\u5b9e\u672c\u8d28\u4e0a\u5df2\u7ecf\u5728\u9898\u76ee\u8fd9\u884c\u663e\u793a\u4e86\uff1a\u6700\u5927\u5b50\u6811\u548c\u3002\u8fd9\u9053\u9898\u5e76\u4e0d\u662f\u4e8c\u53c9\u6811\uff0c\u4e5f\u6ca1\u6709\u6307\u660e\u5de6\u8fb9\u8fd8\u662f\u53f3\u8fb9\u662f\u7236\u8282\u70b9\uff0c\u56e0\u6b64\u9ed8\u8ba4\u5de6\u8fb9\u662f\u5b50\u8282\u70b9\uff0c\u53f3\u8fb9\u662f\u7236\u8282\u70b9\uff0c\u4f46\u662f\u8fd9\u6837\u4e00\u6765\u5c31\u4f1a\u6709\u5f88\u591a\u201c\u6839\u8282\u70b9\u201d\u3002\u56e0\u6b64\u9700\u8981\u5bf9\u201c\u591a\u4e2a\u6839\u8282\u70b9\u201d\u8fdb\u884c\u5904\u7406<\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\nint n, v[16005], syb[16005], ans = -0x3f3f3f, dp[16005];\nvector<int> son[16005];\nvector<int> root;\n\nvoid dfs(int x) {\n\tdp[x] = v[x];\n\tfor (int i = 0; i < son[x].size(); i++) {\n\t\tint tar = son[x][i];\n\t\tdfs(tar);\n\t\tif (dp[tar] >= 0) {\n\t\t\tdp[x] += dp[tar];\n\t\t}\n\t}\n\treturn;\n}\n\n\n\nint main() {\n\tios::sync_with_stdio(false);\n\tcin.tie(0);\n\tcin >> n;\n\tfor (int i = 1; i <= n; i++) {\n\t\tcin >> v[i];\n\t\tans = max(ans, v[i]);\n\t}\n\tint x, y;\n\tfor (int i = 1; i <= n - 1; i++) {\n\t\tcin >> x >> y;\n\t\tson[y].push_back(x);\n\t\tsyb[x] = 1;\n\t}\n\tfor (int i = 1; i <= n; i++) {\n\t\tif (!syb[i]) {\n\t\t\troot.push_back(i);\n\t\t}\n\t}\n\tint temp;\n\tfor (int i = 0; i < root.size(); i++) {\n\t\tdfs(root[i]);\n\t\tans = max(ans, dp[root[i]]);\n\t\tif (ans == dp[root[i]]) {\n\t\t\ttemp = i;\n\t\t}\n\t}\n\tfor (int i = 1; i < root.size(); i++) {\n\t\tif (i == temp) {\n\t\t\tcontinue;\n\t\t}\n\t\tif (v[i] < 0) {\n\t\t\tcontinue;\n\t\t}\n\t\tans += v[i];\n\t}\n\n\n\tif (ans < 0) {\n\t\tfor (int i = 1; i <= n; i++) {\n\t\t\tans = max(ans, dp[i]);\n\t\t}\n\t}\n\tcout << ans;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
P1040 [NOIP 2003 \u63d0\u9ad8\u7ec4] \u52a0\u5206\u4e8c\u53c9\u6811<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Part1 \u7ebf\u6027\u52a8\u6001\u89c4\u5212 P2679 [NOIP 2015 \u63d0\u9ad8\u7ec4] \u5b50\u4e32 \u5f88\u6709\u624b\u6cd5\u7684\u4e00\u9053\u52a8\u6001\u89c4\u5212\u3002\u8003\u8651\u7528\u56db\u7ef4 […]<\/p>\n","protected":false},"author":1,"featured_media":695,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19,26],"tags":[],"class_list":["post-676","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data_learning","category-26"],"_links":{"self":[{"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/posts\/676","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/47.121.202.229\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=676"}],"version-history":[{"count":14,"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/posts\/676\/revisions"}],"predecessor-version":[{"id":737,"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/posts\/676\/revisions\/737"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/47.121.202.229\/index.php?rest_route=\/wp\/v2\/media\/695"}],"wp:attachment":[{"href":"http:\/\/47.121.202.229\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=676"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/47.121.202.229\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=676"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/47.121.202.229\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=676"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}