<\/span><\/h4>\n\n\n\n\u9996\u5148\u6211\u5148\u4ecb\u7d39\u6bd4\u8f03\u512a\u7684\u89e3\u6cd5\uff0c\u5229\u7528\u6bd4\u8f03\u5927\u5c0f\u4ee5\u53ca\u7d00\u9304\u5403\u7684\u98df\u7269\u6578\u91cf\u4f86\u9032\u884c\u8655\u7406\u3002
\u6211\u5011\u9996\u5148\u8981\u53bb\u601d\u8003\u984c\u76ee\u8981\u7684\u6771\u897f\u662f\u4ec0\u9ebc\u5462 -> \u4e00\u5171\u6709\u5169\u500b\u6771\u897f\uff1a1. \u6700\u591a\u7684\u98df\u7269 2. \u6700\u5f8c\u5403\u7684\u98df\u7269\u4f4d\u7f6e
\u90a3\u8981\u600e\u9ebc\u77e5\u9053\u5de6\u908a\u7684\u98df\u7269\u6bd4\u8f03\u591a\u9084\u662f\u53f3\u908a\u7684\u98df\u7269\u6bd4\u8f03\u591a\u5462 -> \u7528\u5169\u500b\u8b8a\u6578\u7d00\u9304\u5f80\u5de6\u908a\u5403\u591a\u5c11\u5f80\u53f3\u908a\u5403\u591a\u5c11
\u8981\u600e\u9ebc\u7d00\u9304\u6700\u5de6\u908a\u7684\u98df\u7269\u6216\u662f\u6700\u53f3\u908a\u7684\u98df\u7269 -> \u7528\u5169\u500b\u8b8a\u6578\uff0c\u4e00\u500b\u7d00\u9304\u6700\u5927\u503c\u4e00\u500b\u7d00\u9304\u6700\u5c0f\u503c
\u6839\u64da\u4ee5\u4e0a\u60f3\u6cd5\u61c9\u8a72\u53ef\u4ee5\u505a\u51fa\u5982\u4e0b\u7684\u7a0b\u5f0f\u78bc\u3002<\/p>\n\n\n\n
#Python\nx,n = [int(i) for i in input().split()]\nnumList = [int(i) for i in input().split()]#\u628a\u98df\u7269\u5ea7\u6a19\u5b58\u5230numList\nmaxNum,minNum = -101,101#\u98df\u7269\u7684\u6700\u5927\u5ea7\u6a19\u3001\u98df\u7269\u7684\u6700\u5c0f\u5ea7\u6a19\nleft,right = 0,0#\u5f80\u5de6\u53f3\u5403\u7684\u98df\u7269\u6578\u91cf\nfor i in numList:#\u8b80\u53d6\u98df\u7269\u5ea7\u6a19 i:\u98df\u7269\u5ea7\u6a19 X:\u8001\u9f20\u5ea7\u6a19\n if i > x:#\u98df\u7269\u5728\u8001\u9f20\u53f3\u908a\n right = right + 1#\u53f3\u908a\u98df\u7269\u591a\u4e00\n maxNum = max(maxNum,i)#\u6bd4\u8f03\u8001\u9f20\u53f3\u908a\u7684\u5ea7\u6a19\u5927\u5c0f\n if i < x:#\u98df\u7269\u5728\u8001\u9f20\u5de6\u908a\n left = left + 1\n minNum = min(minNum,i)\nif left > right:#\u5de6\u908a\u98df\u7269\u8f03\u591a\n print(left,minNum)\nelse:\n print(right,maxNum)<\/code><\/pre>\n\n\n\n\/\/C++\n#include <iostream>\nusing namespace std;\nint main(){\n int x,n;\n cin>>x>>n;\n int maxNum,minNum;\n int left,right;\n maxNum = -101;\/\/\u98df\u7269\u7684\u6700\u5927\u5ea7\u6a19\n minNum = 101;\/\/\u98df\u7269\u7684\u6700\u5c0f\u5ea7\u6a19\n left = right = 0;\/\/\u5f80\u5de6\u53f3\u5403\u7684\u98df\u7269\u6578\u91cf\n for(int i = 0;i<n;i++){\/\/temp:\u98df\u7269\u5ea7\u6a19 X:\u8001\u9f20\u5ea7\u6a19\n int temp;\n cin>>temp;\/\/\u76f4\u63a5\u9032\u884c\u8f38\u5165\u98df\u7269\u5ea7\u6a19\n if (temp>x){\/\/\u98df\u7269\u5728\u8001\u9f20\u53f3\u908a\n right++;\/\/\u53f3\u908a\u98df\u7269\u591a\u4e00\n if(temp>maxNum){\/\/\u6bd4\u8f03\u8001\u9f20\u53f3\u908a\u7684\u5ea7\u6a19\u5927\u5c0f\n maxNum = temp;\n }\n }\n if (temp<x){\/\/\u98df\u7269\u5728\u8001\u9f20\u5de6\u908a\n left++;\/\/\u5de6\u908a\u98df\u7269\u591a\u4e00\n if(temp<minNum){\/\/\u6bd4\u8f03\u8001\u9f20\u5de6\u908a\u7684\u5ea7\u6a19\u5927\u5c0f\n minNum = temp;\n }\n }\n }\n if (left > right){\/\/\u5de6\u908a\u98df\u7269\u8f03\u591a\n cout<<left<<\" \"<<minNum;\n }else{\n cout<<right<<\" \"<<maxNum;\n }\n} <\/code><\/pre>\n\n\n\n<\/span>\u6a5f\u68b0\u9f20\u7b2c\u4e8c\u500b\u505a\u6cd5 \uff1a\u6392\u5e8f<\/span><\/h4>\n\n\n\n\u63a5\u4e0b\u4f86\u662f\u6392\u5e8f\u7684\u9019\u500b\u65b9\u6cd5\uff0c\u60f3\u6cd5\u5f88\u7c21\u55ae\uff0c\u65e2\u7136\u6578\u7dda\u6c92\u6709\u6392\u5217\u597d\u90a3\u6211\u5011\u5c31\u5e6b\u4ed6\u6392\u5217\uff0c\u4e26\u4e14\u628a\u8001\u9f20\u7684\u4f4d\u7f6e\u4e5f\u653e\u9032\u53bb\uff0c\u6703\u5f62\u6210\u4ee5\u4e0b\u5716\u5f62\uff0c\u6b64\u6642\u5c31\u6c92\u6709\u5148\u5f8c\u554f\u984c\u3002<\/p>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/\u6a5f\u68b0\u9f202.jpg?resize=1024%2C576&ssl=1\")
<\/figure>\n\n\n\n\u6b64\u6642\u6211\u5011\u53ea\u9700\u8981\u505a\u4ee5\u4e0b\u4e8b\u60c5\uff1a
1. \u77e5\u9053\u8001\u9f20\u5728\u9019\u500b\u6578\u5217\u88e1\u9762\u7684\u7d22\u5f15\u503c
2. \u900f\u904e\u7d22\u5f15\u503c\u5373\u53ef\u77e5\u5de6\u908a\u5403\u591a\u5c11\uff0c\u53f3\u908a\u5403\u591a\u5c11
3. \u6bd4\u8f03\u5de6\u53f3\u54ea\u908a\u5403\u6bd4\u8f03\u591a\u6c7a\u5b9a\u8f38\u51fa\u7b2c0\u500b\u5ea7\u6a19\u6216\u662f\u6700\u5f8c\u4e00\u500b\u5ea7\u6a19<\/p>\n\n\n\n
#Python\nx,n = [int(i) for i in input().split()]\nnumList = [int(i) for i in input().split()]\nnumList.append(x)\nnumList.sort()\nindex = numList.index(x)#\u53ef\u7528\u4e8c\u641c\u4ee3\u66ff\nif index > n - index:\n print(index,numList[0])\nelse:\n print(n-index,numList[-1])<\/code><\/pre>\n\n\n\n\/\/C++\n#include<iostream>\n#include<vector>\n#include<algorithm>\nusing namespace std;\n\nint main() {\n int x, n;\n cin >> x >> n;\n\n vector<int> numList(n);\n for(int i = 0; i < n; ++i) {\n cin >> numList[i];\n }\n\n numList.push_back(x);\n sort(numList.begin(), numList.end());\n\n int index = find(numList.begin(), numList.end(), x) - numList.begin();\n\n if (index > n - index) {\n cout << index << \" \" << numList[0] << endl;\n } else {\n cout << n - index << \" \" << numList.back() << endl;\n }\n\n return 0;\n}\n<\/code><\/pre>\n\n\n\n<\/span>\u5361\u724c\u904a\u6232<\/span><\/h2>\n\n\n\n\u984c\u76ee\u7c21\u8ff0\uff1a
\u6709\u4e00\u500bn x m\u7684\u8868\u683c\u88e1\u9762\u586b\u6eff\u4e86\u6578\u5b57\uff0c\u6bcf\u500b\u6578\u5b57\u525b\u597d\u51fa\u73fe\u5169\u6b21\u3002
\u6d88\u9664\u5169\u500b\u76f8\u540c\u6578\u503c\u76f8\u540c\u4e14\u4e2d\u9593\u6c92\u6709\u963b\u9694\u5176\u4ed6\u969c\u7919\u7269\u7684\u6578\u5b57 x \u6642\u53ef\u4ee5\u7372\u5f97 x \u5206\u3002
\u53ef\u4ee5\u5782\u76f4\u6216\u8005\u5e73\u884c\u6d88\u9664\uff0c\u4f46\u4e2d\u9593\u4e0d\u53ef\u963b\u9694\u5176\u4ed6\u6578\u503c\u3002
\u53ef\u53c3\u8003\u4ee5\u4e0b\u793a\u610f\u5716<\/p>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/\u5361\u724c\u904a\u62321.png?resize=1024%2C396&ssl=1\")
\u5171\u6709\u5076\u6578\u7a2e\u6578\u5b57\uff0c\u5206\u6563\u5728\u8868\u683c\u7684\u5404\u500b\u5730\u65b9\uff0c\u627e\u51fa\u76f8\u9130\u7684\u6578\u5b57\u4e26\u6d88\u9664\u5b83\u5011<\/figcaption><\/figure>\n\n\n\n\u9019\u984c\u5728\u77e9\u9663\u88e1\u7b97\u662f\u4e00\u984c\u6eff\u57fa\u672c\u7684\u984c\u76ee\uff0c\u53ea\u8981\u80fd\u5920\u6b63\u5e38\u5730\u8b80\u53d6\u77e9\u9663\uff0c\u61c9\u8a72\u90fd\u5beb\u5f97\u51fa\u9019\u4e00\u984c\uff0c\u9019\u908a\u63d0\u4f9b\u5169\u7a2e\u505a\u6cd5\u3002<\/p>\n\n\n\n
<\/span>\u5361\u724c\u904a\u6232\u7b2c\u4e00\u500b\u505a\u6cd5\uff1a\u53ea\u8655\u7406\u300c\u5217\u300d + \u65cb\u8f49\u77e9\u9663<\/span><\/h4>\n\n\n\n\u9996\u5148\u9019\u984c\u76ee\u5176\u5be6\u5206\u6210\u4e0a\u4e0b\u5169\u5b50\u984c
\u7b2c\u4e00\u5b50\u984c\u70ba60% n = 1\uff0c\u4e5f\u5c31\u662f\u8aaa\u53ea\u6709\u4e00\u5217\u7684\u72c0\u6cc1<\/p>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/\u5361\u724c\u904a\u62322.jpg?resize=1024%2C576&ssl=1\")
\u5982\u679c\u5f9e\u4e00\u822c\u7684\u8996\u89d2\u4f86\u53bb\u89c0\u5bdf\u9019\u984c\u7684\u8a71\u61c9\u8a72\u6703\u7522\u751f\u5982\u4e0a\u5716\u7684\u72c0\u6cc1\uff0c\u4f46\u7531\u65bc\u6211\u5011\u662f\u8dd1\u7a0b\u5f0f\u8b80\u53d6\u6771\u897f\u6642\u57fa\u672c\u4e0a\u90fd\u662f\u7531\u5de6\u81f3\u53f3\u8b80\u53d6\uff0c\u56e0\u6b64\u9019\u984c\u5176\u5be6\u53ef\u4ee5\u642d\u914dstack\u7684\u6280\u5de7\u7522\u751f\u51fa\u4ee5\u4e0b\u7684\u6548\u679c\u3002<\/figcaption><\/figure>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/\u5361\u724c\u904a\u6232.gif?resize=770%2C330&ssl=1\")
<\/figure>\n\n\n\n\u5982\u6b64\u4e00\u4f86\u5c31\u6709\u4e86\u300c\u53ea\u6709\u4e00\u5217\u300d\u7684\u89e3\u6c7a\u65b9\u6848\uff0c\u56e0\u6b64\u82e5\u6211\u5011\u628a\u9019\u65b9\u6848\u7531\u4e0a\u5f80\u4e0b\u57f7\u884c\u4e00\u6b21\uff0c\u5c31\u53ef\u4ee5\u5b8c\u6210\u6240\u6709\u5217\u7684\u5206\u6578\u52a0\u7e3d\u3002
\u4f46\u6b64\u6642\u5c31\u6703\u9047\u5230\u4e0b\u4e00\u500b\u554f\u984c\uff1a\u300c\u884c\u300d\u7684\u90e8\u5206\u8981\u600e\u9ebc\u8655\u7406\u5462\uff1f\u6211\u9019\u908a\u7684\u89e3\u6c7a\u65b9\u6848\u70ba\u884c\u5217\u5c0d\u8abf\uff0c\u53ea\u8981\u628a\u884c\u8b8a\u6210\u5217\uff0c\u518d\u7528\u76f8\u540c\u4f5c\u6cd5\u505a\u4e00\u904d\u5373\u53ef\u3002\u63a5\u8457\u5c31\u662f\u4e0d\u65b7\u57f7\u884c\u6b64\u904e\u7a0b\uff0c\u76f4\u5230\u5206\u6578\u6c92\u6709\u589e\u52a0\u70ba\u6b62\u3002
\u9019\u6a23\u505a\u6cd5\u7684\u6700\u5927\u597d\u8655\u662f\uff0c\u5b8c\u5168\u4e0d\u7528\u64d4\u5fc3\u884c\u5217\u641e\u6df7\uff0c\u6211\u5011\u53ea\u8981\u5c08\u6ce8\u5728\u884c\u7684\u8655\u7406\u5c31\u53ef\u4ee5\u4e86\u3002<\/p>\n\n\n\n
#Python\ndef reGroup(matrix,score):\n flag = 0\n newMaxtrix = []\n for numList in matrix:\n numList = list(numList)\n stack = []\n for i in range(len(numList)):#\u8b80\u53d6numList\u88e1\u9762\u7684\u6771\u897f\n if numList[i] == -1:\n continue\n if stack:\n if stack[-1][-1] == numList[i]:\n index,value = stack.pop()\n numList[i],numList[index] = -1,-1\n score += value\n flag = 1\n else:\n stack.append((i,numList[i]))\n else:\n stack.append((i,numList[i]))\n newMaxtrix.append(numList)\n return newMaxtrix,score,flag\nn,m = [int(i) for i in input().split()]\nmatrix = [[int(j) for j in input().split()] for i in range(n)]\nmatrix,result,no = reGroup(matrix,0)\nflag = 1\nif n == 1:\n print(result)\nelse:\n while flag:\n matrix = list(zip(*matrix))\n matrix,temp,flag = reGroup(matrix,0)\n result += temp\n print(result)\n<\/code><\/pre>\n\n\n\n\/\/C++\n#include <iostream>\n#include <vector>\nusing namespace std;\n\/\/\u884c\u5217\u5c0d\u8abf\nvector<vector<int>> transMatrix(vector<vector<int>>& matrix) {\n int rows = matrix.size();\n int cols = matrix[0].size();\n \/\/ \u5275\u5efa\u4e00\u500b\u65b0\u7684\u4e8c\u7dad vector \u4f86\u5b58\u5132\u8f49\u7f6e\u5f8c\u7684\u77e9\u9663\n vector<vector<int>> transposedMatrix(cols, vector<int>(rows));\n for(int i = 0; i < rows; ++i) {\n for(int j = 0; j < cols; ++j) {\n \/\/ \u5c07\u539f\u59cb\u77e9\u9663\u7684\u884c\u5143\u7d20\u8a2d\u7f6e\u70ba\u65b0\u77e9\u9663\u7684\u5217\u5143\u7d20\n transposedMatrix[j][i] = matrix[i][j];\n }\n }\n return transposedMatrix;\n}\nlong long getAns(vector<vector<int>>& matrix){\n int flag = 1;\n long long score = 0;\n do {\n \n for (auto &numList : matrix) {\n vector<int> indexStack;\n vector<int> valueStack;\n for (int i = 0; i < numList.size(); i++) {\n if (numList[i] == -1) continue;\n if (!indexStack.empty()) {\n if (valueStack.back() == numList[i]) {\n int index = indexStack.back(); indexStack.pop_back();\n int value = valueStack.back(); valueStack.pop_back();\n numList[i] = numList[index] = -1;\n score += value;\n flag = 1;\n } else {\n indexStack.push_back(i);\n valueStack.push_back(numList[i]);\n }\n } else {\n indexStack.push_back(i);\n valueStack.push_back(numList[i]);\n }\n }\n }\n matrix = transMatrix(matrix);\n if(flag == 0){\n break;\n }\n flag = 0;\n }while(1);\n return score;\n}\nint main(){\n int n,m;\n cin>>n>>m;\n vector<vector<int>> matrix(n, vector<int>(m));\n for(int i = 0; i < n; ++i) {\n for(int j = 0; j < m; ++j) {\n cin >> matrix[i][j];\n }\n }\n long long result;\n result = getAns(matrix);\n cout<<result;\n} <\/code><\/pre>\n\n\n\n<\/span> \u5361\u724c\u904a\u6232\u7b2c\u4e8c\u500b\u505a\u6cd5\uff1a\u884c\u5217\u4e00\u540c\u8655\u7406\uff0c\u8655\u7406\u53f3\u908a\u4ee5\u53ca\u4e0b\u908a<\/span><\/h4>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/\u5361\u724c\u904a\u62322-1.png?resize=1024%2C557&ssl=1\")
\u4ee5\u4e00\u500b\u55ae\u5143\u70ba\u57fa\u6e96\uff0c\u5411\u53f3\u5411\u4e0b\u6162\u6162\u5c0d\u7167\u3002<\/figcaption><\/figure>\n\n\n\n\u57fa\u672c\u4e0a\u4f86\u8aaa\u8207\u7b2c\u4e00\u500b\u505a\u6cd5\u6c92\u6709\u5dee\u592a\u591a\uff0c\u4f46\u500b\u4eba\u8a8d\u70ba\u300c\u884c\u300d\u7684\u8655\u7406\u6bd4\u300c\u5217\u300d\u9ebb\u7169\uff0c\u56e0\u6b64\u6211\u9996\u9078\u4e0d\u662f\u9019\u500b\u505a\u6cd5\u3002<\/p>\n\n\n\n
#Python\nn,m = [int(i) for i in input().split()]\nmatrix = [[int(j) for j in input().split()] for i in range(n)]\n# read matrix and add sentinel\nscore = 0\nwhile True:\n flag = 0\n for i in range(n):\n stack1 = []#\u53f3\n for j in range(m):\n if matrix[i][j] == -1:\n continue\n #\u53f3\n if stack1:\n if stack1[-1][-1] == matrix[i][j]:\n index,value = stack1.pop()\n matrix[i][j],matrix[i][index] = -1,-1\n score += value\n flag = 1\n else:\n stack1.append((j,matrix[i][j]))\n else:\n stack1.append((j,matrix[i][j]))\n #\u4e0b\n stack2 = []#\u4e0b\n for si in range(i,n):\n if matrix[si][j] == -1:\n continue\n if stack2:\n if stack2[-1][-1] == matrix[si][j]:\n index,value = stack2.pop()\n matrix[si][j],matrix[index][j] = -1,-1\n score += value\n flag = 1\n else:\n stack2.append((i,matrix[si][j]))\n else:\n stack2.append((i,matrix[si][j]))\n if flag == 0:\n break\nprint(score) <\/code><\/pre>\n\n\n\n\/\/C++\n#include <iostream>\n#include <vector>\nusing namespace std;\n\nint main() {\n int n, m;\n cin >> n >> m;\n vector<vector<int>> matrix(n, vector<int>(m));\n \n \/\/ \u8b80\u53d6\u77e9\u9663\n for(int i = 0; i < n; ++i) {\n for(int j = 0; j < m; ++j) {\n cin >> matrix[i][j];\n }\n }\n\n int score = 0;\n bool flag;\n\n do {\n flag = false;\n \/\/ \u904d\u6b77\u77e9\u9663\u7684\u6bcf\u4e00\u884c\n for(int i = 0; i < n; ++i) {\n vector<pair<int, int>> stack1; \/\/ \u7528\u65bc\u6aa2\u67e5\u5411\u53f3\n \n for(int j = 0; j < m; ++j) {\n if(matrix[i][j] == -1) continue;\n \/\/ \u6aa2\u67e5\u5411\u53f3\n if(!stack1.empty() && stack1.back().second == matrix[i][j]) {\n pair<int, int> top = stack1.back();\n stack1.pop_back();\n matrix[i][j] = matrix[i][top.first] = -1;\n score += top.second;\n flag = true;\n } else {\n stack1.emplace_back(j, matrix[i][j]);\n }\n\n \/\/ \u6aa2\u67e5\u5411\u4e0b\n vector<pair<int, int>> stack2; \/\/ \u7528\u65bc\u6aa2\u67e5\u5411\u4e0b\n for(int si = i; si < n; ++si) {\n if(matrix[si][j] == -1) continue;\n if(!stack2.empty() && stack2.back().second == matrix[si][j]) {\n pair<int, int> top = stack2.back();\n stack2.pop_back();\n matrix[si][j] = matrix[top.first][j] = -1;\n score += top.second;\n flag = true;\n } else {\n stack2.emplace_back(si, matrix[si][j]);\n }\n }\n }\n }\n } while(flag); \/\/ \u82e5 flag \u70ba false\uff0c\u5247\u7d42\u6b62\u5faa\u74b0\n\n cout << score << endl;\n\n return 0;\n}\n<\/code><\/pre>\n\n\n\n<\/span>\u642c\u5bb6 <\/span><\/h2>\n\n\n\n\u984c\u76ee\u7c21\u8ff0\uff1a
\u6709\u4e00 n x m \u7684\u77e9\u9663\uff0c\u6709\u4e03\u7a2e\u6c34\u7ba1\u6703\u81f3\u65bc\u77e9\u9663\u7576\u4e2d\uff0c\u6c42\u6c34\u7ba1\u6700\u591a\u9023\u901a\u591a\u5c11\u683c\uff1f<\/p>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/\u642c\u5bb61-2.jpg?resize=1024%2C576&ssl=1\")
<\/figure>\n\n\n\n
\u57fa\u672c\u4e0a\u53ea\u8981\u770b\u5230\u9019\u7a2e\u7b97\u683c\u5b50\u7684\u984c\u76ee\u90fd\u6703\u662f\u5c6c\u65bcGraph\u76f8\u95dc\u984c\u578b\uff0c\u800c\u4e14\u901a\u5e38\u53ef\u4ee5\u7528BFS(\u5ee3\u5ea6\u512a\u5148\u641c\u5c0b\u6cd5)\u6216\u8005DPS(\u6df1\u5ea6\u512a\u5148\u641c\u5c0b\u6cd5)\u9032\u884c\u89e3\u6c7a\u3002<\/p>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/\u642c\u5bb61-2.png?resize=1024%2C588&ssl=1\")
\u5982\u540c\u9019\u5f35\u5716\u793a\uff0c\u53d7\u5148\u7b2c\u4e00\u500b\u9023\u901a\u7ba1\u70baXH7JHL\u5171\u516d\u500b\uff0c\u7b2c\u4e8c\u500b\u9023\u901a\u7ba1\u6709H7I\u5171\u4e09\u500b\uff0c\u7b2c\u4e09\u500b\u9023\u901a\u7ba1\u6709IXIIXJ\u5171\u516d\u500b\uff0c\u7b2c\u56db\u500b\u9023\u901a\u7ba1\u6709HH\u5171\u4e8c\u500b\uff0c\u7b2c\u4e94\u500b\u9023\u901a\u7ba1\u6709HHJ\u5171\u4e09\u500b\uff0c\u7b2c\u516d\u500b\u9023\u901a\u7ba1\u6709I\u5171\u4e00\u500b\u3002\u56e0\u6b64\u6700\u591a\u5c31\u53ea\u6709\u516d\u683c\u9023\u901a\u7ba1\u3002<\/figcaption><\/figure>\n\n\n\n\u9019\u984c\u5728\u89e3\u984c\u7684\u6642\u5019\u6709DFS\u8ddfBFS\u7684\u65b9\u5f0f\u53ef\u4ee5\u89e3\u984c\uff0c\u4f46\u7576\u770b\u52301<=n,m<=500\u6642\u5c31\u8981\u6ce8\u610f\u5230\u7a7a\u9593\u8907\u96dc\u5ea6\u7684\u554f\u984c\uff0c\u56e0\u6b64\u5de6\u53f3\u8861\u91cf\u5f8c\u9084\u662f\u6c7a\u5b9a\u4f7f\u7528BFS\u6703\u6bd4\u8f03\u7a69\u59a5\u3002<\/p>\n\n\n\n
<\/span>\u642c\u5bb6BFS\u89e3\u6cd5<\/span><\/h4>\n\n\n\n\u9019\u984c\u89e3\u984c\u91cd\u9ede\u5728\u65bc\u5169\u9ede
1. \u6c34\u7ba1\u53ef\u4ee5\u9023\u901a\u7684\u65b9\u5411 -> \u5229\u7528map\u7684\u65b9\u5f0f\u9650\u5b9a\u53ef\u4ee5\u8d70\u7684\u65b9\u5411
2. \u9023\u901a\u7ba1\u5f62\u6210\u8ff4\u8def\u6642\u7684\u8655\u7406\u65b9\u5f0f -> \u7d00\u9304\u8d70\u904e\u7684\u5730\u65b9
\u7167\u6211\u9019\u6a23\u5beb\u770b\u8d77\u4f86\u6703\u6bd4\u8f03\u6e05\u695a\uff0c\u4f46\u7f3a\u9ede\u662f\u6642\u9593\u8907\u96dc\u5ea6\u6703\u504f\u9ad8\uff0c\u57f7\u884c\u6548\u7387\u6703\u6bd4\u8f03\u4f4e\u4e00\u9ede\u3002
\u5236\u5b9a\u5b8c\u4e4b\u5f8c\u63a5\u4e0b\u4f86\u8981\u8dd1\u7684\u5c31\u662f\u6b63\u5e38\u7684BFS\u7684\u6d41\u7a0b\u3002<\/p>\n\n\n\n
#Python\n#X:\u4e0a\u4e0b\u5de6\u53f3\n#I:\u4e0a\u4e0b\n#H:\u5de6\u53f3\n#L:\u53f3\u4e0a\n#7:\u5de6\u4e0b\n#F:\u53f3\u4e0b\n#J:\u5de6\u4e0a\n#0:\u6c92\u6709\u6c34\u7ba1\n#\u8981\u78ba\u8a8d\u662f\u5426\u9023\u901a\nn,m = [int(i) for i in input().split()]\nmatrix = [list(input()) for i in range(n)]#\u77e9\u9663\nd = {\"I\":[(-1,0),(1,0)],\"H\":[(0,1),(0,-1)],\"L\":[(-1,0),(0,1)],\"7\":[(0,-1),(1,0)],\"F\":[(1,0),(0,1)],\"J\":[(0,-1),(-1,0)],\"X\":[(1,0),(0,1),(-1,0),(0,-1)]}\n#d\u70ba\u5404\u9023\u901a\u7ba1\u53ef\u4ee5\u9023\u901a\u4e4b\u65b9\u4f4d\nd2 = {(1,0):\"XILJ\",(-1,0):\"XI7F\",(0,1):\"XH7J\",(0,-1):\"XHLF\"}\n#d2\u70ba\u8a72\u65b9\u4f4d\u53ef\u4ee5\u9023\u901a\u5230\u7684\u9023\u901a\u7ba1\nmaxScore = 0\nfor i in range(n):\n for j in range(m):\n if matrix[i][j] != \"0\":\n queue = [(i,j,d[matrix[i][j]])]\n matrix[i][j] = \"0\"\n pointer = 0\n while pointer < len(queue):\n x,y,direction = queue[pointer]\n for dir in direction:\n newX,newY = x+dir[0],y+dir[1]\n if 0 <= newX < n and 0 <= newY < m and matrix[newX][newY] in d2[(dir[0],dir[1])]:\n queue.append((newX,newY,d[matrix[newX][newY]]))\n matrix[newX][newY] = \"0\"\n pointer += 1\n maxScore = max(maxScore,len(queue))\nprint(maxScore)\n<\/code><\/pre>\n\n\n\n\/\/C++\n\/\/\u4e26\u975e\u6700\u512a\u5beb\u6cd5\n#include <iostream>\n#include <vector>\n#include <queue>\n#include <map>\n#include <set>\n#include <tuple>\n\nusing namespace std;\n\n\/\/ \u52a9\u624b\u51fd\u6578\u4f86\u8f38\u51fa\u6700\u5927\u5f97\u5206\nvoid printMaxScore(int n, int m, vector<vector<char>>& matrix) {\n map<char, vector<pair<int, int>>> d = {\n {'I', {{-1, 0}, {1, 0}}},\n {'H', {{0, 1}, {0, -1}}},\n {'L', {{-1, 0}, {0, 1}}},\n {'7', {{0, -1}, {1, 0}}},\n {'F', {{1, 0}, {0, 1}}},\n {'J', {{0, -1}, {-1, 0}}},\n {'X', {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}}\n };\n \n map<pair<int, int>, string> d2 = {\n {{1, 0}, \"XILJ\"},\n {{-1, 0}, \"XI7F\"},\n {{0, 1}, \"XH7J\"},\n {{0, -1}, \"XHLF\"}\n };\n\n int maxScore = 0;\n for (int i = 0; i < n; ++i) {\n for (int j = 0; j < m; ++j) {\n if (matrix[i][j] != '0') {\n queue<tuple<int, int, vector<pair<int, int>>>> q;\n q.push(make_tuple(i, j, d[matrix[i][j]]));\n matrix[i][j] = '0';\n int currentScore = 0;\n \n while (!q.empty()) {\n auto [x, y, direction] = q.front();\n q.pop();\n ++currentScore;\n \n for (auto& dir : direction) {\n int newX = x + dir.first;\n int newY = y + dir.second;\n if (newX >= 0 && newX < n && newY >= 0 && newY < m && \n d2[{dir.first, dir.second}].find(matrix[newX][newY]) != string::npos) {\n q.push(make_tuple(newX, newY, d[matrix[newX][newY]]));\n matrix[newX][newY] = '0';\n }\n }\n }\n maxScore = max(maxScore, currentScore);\n }\n }\n }\n cout << maxScore << endl;\n}\n\nint main() {\n int n, m;\n cin >> n >> m;\n cin.ignore(); \/\/ \u5ffd\u7565\u5728\u8b80\u53d6\u6574\u6578\u8f38\u5165\u5f8c\u7684\u63db\u884c\u7b26\n vector<vector<char>> matrix(n, vector<char>(m));\n for (int i = 0; i < n; ++i) {\n for (int j = 0; j < m; ++j) {\n cin >> matrix[i][j];\n }\n }\n\n printMaxScore(n, m, matrix);\n return 0;\n}\n <\/code><\/pre>\n\n\n\n<\/span>\u642c\u5bb6DFS\u89e3<\/span><\/h4>\n\n\n\n\u500b\u4eba\u5617\u8a66\u5f8c\u662f\u4e0d\u5efa\u8b70\u4f7f\u7528DFS\u89e3\uff0c\u78ba\u5be6\u6703\u6709\u7a7a\u9593\u7684\u554f\u984c\uff0c\u56e0\u6b64\u9019\u908a\u6211\u53ea\u9644\u4e0aPython\u89e3\u6cd5\u3002<\/p>\n\n\n\n
n, m = [int(i) for i in input().split()]\nmatrix = [list(input()) for _ in range(n)] # \u77e9\u9663\n\n# \u5404\u985e\u578b\u6c34\u7ba1\u53ef\u9023\u901a\u7684\u65b9\u5411\nd = {\n \"I\": [(-1, 0), (1, 0)],\n \"H\": [(0, 1), (0, -1)],\n \"L\": [(-1, 0), (0, 1)],\n \"7\": [(0, -1), (1, 0)],\n \"F\": [(1, 0), (0, 1)],\n \"J\": [(0, -1), (-1, 0)],\n \"X\": [(1, 0), (0, 1), (-1, 0), (0, -1)]\n}\n\n# \u5f9e\u7d66\u5b9a\u65b9\u5411\u53ef\u9023\u63a5\u7684\u6c34\u7ba1\u985e\u578b\nd2 = {\n (1, 0): \"XILJ\",\n (-1, 0): \"XI7F\",\n (0, 1): \"XH7J\",\n (0, -1): \"XHLF\"\n}\n\n# \u57f7\u884c DFS \u7684\u51fd\u6578\ndef dfs(x, y):\n if not (0 <= x < n and 0 <= y < m) or matrix[x][y] == \"0\":\n return 0\n \n # \u8a08\u7b97\u9019\u584a\u6c34\u7ba1\n count = 1\n pipe_type = matrix[x][y]\n matrix[x][y] = \"0\" # \u6a19\u8a18\u70ba\u5df2\u8a2a\u554f\n \n # \u63a2\u7d22\u6240\u6709\u53ef\u9023\u901a\u65b9\u5411\n for dx, dy in d[pipe_type]:\n nx, ny = x + dx, y + dy\n if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] in d2[(dx, dy)]:\n count += dfs(nx, ny)\n return count\n\n# \u904d\u6b77\u6bcf\u500b\u55ae\u5143\u683c\u4ee5\u627e\u5230\u6700\u5927\u7684\u9023\u901a\u7ba1\u7fa4\nmax_score = 0\nfor i in range(n):\n for j in range(m):\n if matrix[i][j] != \"0\":\n max_score = max(max_score, dfs(i, j))\n\nprint(max_score)\n <\/code><\/pre>\n\n\n\n<\/span>\u6295\u8cc7\u904a\u6232<\/span><\/h2>\n\n\n\n\u984c\u76ee\u7c21\u8ff0\uff1a
\u4f60\u64c1\u6709\u4e00\u500b\u9577\u5ea6\u70ba n \u7684\u9663\u5217\uff0c\u4ee3\u8868\u6bcf\u5929\u7684\u6295\u8cc7\u6536\u76ca\uff0c\u4ee5\u53ca k (k<=20)\u5f35\u91d1\u724c\u3002
\u4f60\u53ef\u4ee5\u81ea\u884c\u6c7a\u5b9a\u6295\u8cc7\u7684\u958b\u59cb\u548c\u7d50\u675f\u65e5\u671f\u3002\u5728\u4f60\u9078\u64c7\u6295\u8cc7\u7684\u6bcf\u4e00\u5929\uff0c\u4f60\u53ef\u4ee5\u9078\u64c7\u6d88\u8017\u4e00\u5f35\u91d1\u724c\u4f86\u8df3\u904e\u7576\u5929\uff0c\u6216\u8005\u4e0d\u4f7f\u7528\u91d1\u724c\u800c\u62ff\u53d6\u7576\u5929\u7684\u6536\u76ca\u3002\u4f60\u7684\u76ee\u6a19\u662f\u627e\u51fa\u5982\u4f55\u6295\u8cc7\uff0c\u4ee5\u5be6\u73fe\u6700\u5927\u7684\u7e3d\u6536\u76ca\u3002
\u8acb\u6ce8\u610f\uff0c\u4f60\u53ea\u80fd\u5728\u6295\u8cc7\u671f\u9593\u9032\u51fa\u4e00\u6b21\u3002<\/p>\n\n\n\n
\u7b97\u662f\u4e00\u500b\u6eff\u57fa\u672c\u7684dp(\u52d5\u614b\u898f\u5283)\u984c\u76ee\uff0c\u76f4\u63a5\u7528\u52d5\u614b\u898f\u5283\u7684\u65b9\u5f0f\u9032\u884c\u89e3\u7b54\u53ef\u4ee5\u5f97\u5230\u5feb\u901f\u4e14\u7c21\u77ed\u7684\u89e3\u7b54\u3002
\u4f46\u500b\u4eba\u5728\u5be9\u984c\u7684\u6642\u5019\u9084\u662f\u7fd2\u6163\u53bb\u6ce8\u610f\u5230\u4e00\u4e9b\u5c0f\u7d30\u7bc0\uff0c\u7562\u7adf\u6211\u5011\u91cd\u9ede\u662f\u4f86\u62ff\u5206\u7684\uff0c\u800c\u4e0d\u662f\u8981\u6c42\u81ea\u5df1\u4e00\u5b9a\u8981\u505a\u51fa\u591a\u5b8c\u7f8e\u7684\u7b54\u6848\uff0c\u56e0\u6b64\u6211\u5011\u9084\u662f\u4f86\u6ce8\u610f\u4e00\u4e0b\u300c\u5b50\u984c\u5206\u6578\u300d\u9019\u4e00part\u5427\u3002<\/p>\n\n\n\n
\u5b50\u984c\u5206\u6578\uff1a<\/strong>
20%\uff1a\u6eff\u8db3 k = 0\uff0c\u4e14 1<=n<=2000\u3002<\/strong>
20%\uff1a\u6eff\u8db3 k = 0\uff0c\u4e14 1<=n<=150000\u3002<\/strong>
60%\uff1a\u6eff\u8db3 1<=k<=20\uff0c1<=n<=150000\u3002<\/strong>
\u4f60\u6703\u770b\u5230\u524d40%\u5176\u5be6\u662f\u6c92\u6709\u4f7f\u7528\u5230\u91d1\u724c\u7684\uff0c\u90a3\u5982\u679c\u6c92\u6709\u4f7f\u7528\u5230\u91d1\u724c\u7684\u8a71\uff0c\u90a3\u5176\u5be6\u6709\u6c92\u6709\u4f7f\u7528\u5230dp\u9019\u9ebc\u65b9\u6cd5\u5c31\u7121\u6240\u8b02\u4e86\u3002\u56e0\u6b64\u91dd\u5c0d\u524d40%\u6211\u4f7f\u7528\u4e86\u5176\u4ed6\u7684\u6280\u5de7\u4f86\u5b8c\u6210\u5b83\u3002<\/p>\n\n\n\n<\/span> \u6295\u8cc7\u904a\u623240%\u89e3\u6cd5(zerojudge\u53ef\u523050%)<\/span><\/h4>\n\n\n\n\u5728\u601d\u8003\u7684\u6642\u5019\u6211\u5011\u53ef\u4ee5\u628a\u5b83\u7576\u6210\u4e00\u500b\u7dda\u5716\u4f86\u53bb\u770b\uff0c\u6bcf\u4e00\u683c\u90fd\u6703\u6709\u53ef\u4ee5\u8cfa\u5230\u7684\u9322\u6216\u8005\u7576\u5929\u6703\u8ce0\u7684\u9322\uff0c\u90a3\u6211\u5011\u8981\u505a\u7684\u4e8b\u60c5\u5c31\u662f\u628a\u6bcf\u4e00\u5929\u7684\u9322\u52a0\u8d77\u4f86\u8b8a\u6210\u4e00\u500b\u7e3d\u548c—-\u6709\u9ede\u50cf\u662fprefix sum\u7684\u6280\u5de7\uff0c\u4f46\u5728\u52a0\u8d77\u4f86\u7684\u540c\u6642\u4e5f\u8981\u6ce8\u610f\u5230\u662f\u5426\u6703\u8b8a\u6210\u300c\u8ca0\u50b5\u300d\u7684\u72c0\u614b\uff0c\u5982\u679c\u6703\u8ca0\u50b5\u7684\u8a71\uff0c\u4ee3\u8868\u524d\u5e7e\u5929\u8cfa\u5f97\u9322\u6beb\u7121\u610f\u7fa9\uff0c\u56e0\u6b64\u5c31\u76f4\u63a5\u6b780\u91cd\u65b0\u958b\u59cb\uff0c\u9047\u5230\u53ef\u4ee5\u8cfa\u9322\u7684\u6642\u5019\u518d\u91cd\u65b0\u9032\u884c\u52a0\u7e3d\u5373\u53ef\u3002\u6700\u5f8c\u627e\u51fa\u6bcf\u6b21\u5f9e0\u958b\u59cb\u5f8c\u7684\u6700\u9ad8\u5cf0\u5373\u53ef\u3002<\/p>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/\u6295\u8cc7\u904a\u62321.png?resize=1024%2C551&ssl=1\")
<\/figure>\n\n\n\n#Python\nn,k = [int(i) for i in input().split()]\nnumList = [int(i) for i in input().split()]\ntotal = 0\nmaxScore = 0\nfor i in range(len(numList)):\n total = max(total,0) + numList[i]\n maxScore = max(total,maxScore)\nprint(maxScore)<\/code><\/pre>\n\n\n\n\/\/C++\n#include <iostream>\n#include <vector>\n#include <algorithm> \/\/ std::max \u51fd\u6578\u9700\u8981\u5f15\u5165\u6b64\u6a19\u982d\u6a94\nusing namespace std;\nint main() {\n int n, k;\n cin >> n >> k;\n vector<int> numList(n); \/\/ \u5efa\u7acb\u4e00\u500b\u5927\u5c0f\u70ba n \u7684\u5411\u91cf\u4f86\u5132\u5b58\u6578\u5b57\n for (int i = 0; i < n; ++i) {\n cin >> numList[i];\n }\n\n int total = 0;\n int maxScore = 0; \n for (int num : numList) {\n total = max(total, 0) + num;\n maxScore = max(total, maxScore);\n }\n\n std::cout << maxScore << std::endl;\n\n return 0;\n}\n<\/code><\/pre>\n\n\n\n<\/span> \u6295\u8cc7\u904a\u6232100%\u89e3\u6cd5(Dynamic Programing)<\/span><\/h4>\n\n\n\n\u5728\u5beb\u52d5\u614b\u898f\u5283\u76f8\u95dc\u984c\u76ee\u7684\u6642\u5019\uff0c\u6211\u5011\u52d9\u5fc5\u8981\u53bb\u627e\u51fa\u4e0a\u4e0b\u9805\u7684\u95dc\u806f\u6027\uff0c\u901a\u5e38\u9019\u662f\u4e00\u500b\u5f88\u9ebb\u7169\u7684\u904e\u7a0b\uff0c\u4f46\u53ea\u8981\u80fd\u5920\u6210\u529f\u5730\u627e\u51fa\u4f86\u7684\u8a71\u7a0b\u5f0f\u78bc\u5176\u5be6\u5c31\u5f88\u597d\u5beb\u4e86\uff0c\u4e5f\u56e0\u6b64\u6211\u5011\u4f86\u69cb\u601d\u4e00\u4e0b\u9019\u500b\u90e8\u5206\u3002
\u9996\u5148\u6211\u5011\u8981\u5148\u4e86\u89e3\u4ee5\u4e0b\u5e7e\u9ede\uff1a
1. \u91d1\u724c\u4e0d\u4e00\u5b9a\u8981\u4f7f\u7528
2. \u91d1\u724c\u662f\u6709\u9650\u7684
3. \u6574\u500b\u6578\u5217\u88e1\u53ef\u80fd\u4e0d\u5230k\u500b\u8ca0\u503c
\u4e86\u89e3\u4ee5\u4e0a\u5e7e\u9ede\u5f8c\u6211\u5011\u518d\u4f86\u601d\u8003\u8a72\u52d5\u614b\u898f\u5283\u7684\u905e\u8ff4\u5f0f\u61c9\u8a72\u8981\u5982\u4f55\u5b8c\u6210\uff0c\u9996\u5148\u6211\u5011\u5148\u4f86\u770b40%\u7684\u3002
(\u4ee5\u4e0b\u90e8\u5206\u70ba\u4f55\u6703\u653e\u7f6e\u5728100%\u88e1\u8aaa\u660e\uff0c\u56e0\u500b\u4eba\u6dfa\u898b\uff0c\u5c31\u7b97\u6c92\u601d\u8003\u5230\u4ee5\u4e0b\u90e8\u5206\u4e5f\u61c9\u56de\u7b54\u5f97\u51fa40%\u89e3\u6cd5)<\/p>\n\n\n\n
total = max(total,0) + numList[i]<\/code><\/pre>\n\n\n\n\u9019\u90e8\u5206\u7a0b\u5f0f\u78bc\u5176\u5be6\u662f\u5df2\u7d93\u7c21\u5316\u5b8c\u7562\u7684\uff0ctotal\u7406\u8ad6\u4e0a\u4f86\u8aaa\u4ed6\u61c9\u8a72\u6703\u662f\u4e00\u500b\u9663\u5217\u7528\u4f86\u5132\u5b58\u6bcf\u65e5\u71df\u5229\u7528
<\/p>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/\u6295\u8cc7\u904a\u62322-2.png?resize=1024%2C628&ssl=1\")
<\/figure>\n\n\n\n\u4e5f\u5c31\u662f\u8aaa\u6211\u5011\u53ef\u4ee5\u77e5\u9053\u8aaa total[i] = max(total[i],0) + numList[i]
\u9019\u5176\u5be6\u5df2\u7d93\u662f\u905e\u8ff4\u7684\u4e00\u500b\u74b0\u7bc0\uff0c\u5b83\u4ee3\u8868\u7684\u5c31\u662f\u6307 0 \u5f35\u91d1\u5361\u7684\u72c0\u6cc1\u3002
(\u81f3\u65bc\u70ba\u4f55\u53ef\u4ee5\u5316\u70batotal\u4e00\u500b\u8b8a\u6578\u5462\uff1f\u56e0\u70ba\u6211\u5011\u53ea\u4f7f\u7528\u5f97\u5230\u76ee\u524d\u7684\u9ad8\u5cf0\u503c\uff0c\u5176\u4ed6\u6771\u897f\u7528\u4e0d\u5230\u53ef\u4ee5\u7701\u7565\u5440\uff01)
\u90a3\u63a5\u4e0b\u4f86100%\u7684\u90e8\u5206\u8a72\u600e\u9ebc\u601d\u8003\u5462\uff1f\u5148\u4f86\u756b\u500b\u8868\u683c\u5427\uff01
\u5148\u5047\u8a2d\u5171\u67092\u5f35\u91d1\u5361\uff0c\u63a5\u4e0b\u4f86 i \u6703\u7528\u4f86\u8868\u793a\u5230\u7b2c\u5e7e\u5929\uff0cj \u662f\u4f7f\u7528\u7684\u91d1\u5361
\u6b64\u6642\u7684\u601d\u8003\u6a21\u5f0f\u8981\u7565\u6709\u4e00\u9ede\u8b8a\u5316\uff0c\u6211\u9700\u8981\u70ba\u6bcf\u5929\u4f7f\u7528\u91d1\u5361\u7684\u72c0\u6cc1\u5efa\u7acb\u8868\u683c\uff0c\u56e0\u70ba\u91d1\u5361\u6709\u9650\u3002\u82e5\u672a\u4f86\u9047\u5230\u65b0\u6578\u64da\u6642\u4e14\u9700\u8981\u4f7f\u7528\u91d1\u5361\u6642\uff0c\u4f46\u767c\u73fe\u91d1\u5361\u524d\u9762\u5df2\u7d93\u7528\u5149\u4e86\uff0c\u53ef\u662f\u53c8\u767c\u73fe\u9019\u6b21\u6578\u64da\u662f\u6bd4\u4e4b\u524d\u7684\u6578\u64da\u66f4\u503c\u5f97\u4f7f\u7528\u91d1\u5361\u7684\uff0c\u90a3\u524d\u9762\u6c92\u6709\u4f7f\u7528\u8868\u683c(recMatrix)\u9032\u884c\u7d00\u9304\u5c31\u5f88\u5c37\u5c2c\u3002
<\/p>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/\u6295\u8cc7\u904a\u62323-2.png?resize=750%2C322&ssl=1\")
<\/figure>\n\n\n\n\u9019\u6642\u5019\u5927\u9ad4\u6c92\u4ec0\u9ebc\u9700\u8981\u6ce8\u610f\u7684\uff0c\u56e0\u70ba\u90fd\u662f\u6b63\u6578\u64da\uff0c\u53ea\u9700\u8981\u597d\u597d\u5730\u4fdd\u5b58\u5373\u53ef\u3002<\/p>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/\u6295\u8cc7\u904a\u62324-2.png?resize=1024%2C511&ssl=1\")
<\/figure>\n\n\n\n\u6b64\u6642\u51fa\u73fe\u4e86\u4e00\u500b\u8ca0\u6578\u64da\uff0c\u6839\u64da\u76ee\u524d\u53ef\u4ee5\u4f7f\u7528\u7684\u91d1\u5361\u53bb\u9032\u884c\u4fdd\u5b58\u3002<\/p>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/\u6295\u8cc7\u904a\u62325-2.png?resize=1024%2C582&ssl=1\")
<\/figure>\n\n\n\n<\/p>\n\n\n\n
\u7b2c\u4e8c\u500b\u8ca0\u6578\u64da\u51fa\u4f86\u4e86\uff0c\u6b64\u6642\u5c31\u53ef\u4ee5\u958b\u59cb\u53bb\u601d\u8003\uff0c\u8868\u683c\u4e0a\u7684\u6578\u5b57\u5230\u5e95\u662f\u5f9e\u54ea\u88e1\u51fa\u4f86\u7684\u3002
\u50cf\u662fk=0\u7684\u90e8\u5206\u6703\u53bb\u6bd4\u8f03\uff0c\u524d\u4e00\u5929\u52a0\u4e0a\u4eca\u5929\u7684\u6578\u64da \u8207 0\u52a0\u4e0a\u4eca\u5929\u7684\u6578\u64da\u8ab0\u6bd4\u8f03\u5927\uff0c\u53ef\u4ee5\u5f88\u55ae\u7d14\u5730\u5f97\u5230\u4ee5\u4e0b\u7a0b\u5f0f\u78bc<\/p>\n\n\n\n
recMatrix[i][0] = max(recMatrix[i-1][0],0) + numList[i]<\/code><\/pre>\n\n\n\n\u90a3\u6709\u91d1\u5361\u6642\u53c8\u8a72\u5982\u4f55\u8655\u7406\u8ca0\u6578\u64da\u5462\uff1f\u6578\u5b57\u53c8\u8a72\u5f9e\u54ea\u88e1\u6293\u5462\uff1f\u6211\u5011\u5148\u4f86\u5c08\u6ce8\u65bc k=1 \u6642 4 \u9019\u500b\u6578\u5b57\u7684\u7522\u751f\u5427\uff01
\u9019\u6642\u5019\u5176\u5be6\u6703\u6709\u500b\u5206\u6b67\u8def\u7dda\uff0c\u56e0\u70ba\u9019\u662f\u7b2c\u4e8c\u500b\u8ca0\u6578\u64da\uff0c\u90a3\u6211\u5011\u5fc5\u9808\u6c7a\u5b9a\u8981\u625b\u54ea\u500b\u8ca0\u6578\u64da\uff0c\u56e0\u6b64\u6211\u5011\u6709\u5169\u500b\u9078\u64c7\u3002
1. \u9078\u53d6\u524d\u4e00\u5929\u6c92\u6709\u4f7f\u7528\u91d1\u5361\u6642\u7684\u91d1\u984d -> \u9019\u4ee3\u8868\u4eca\u5929\u8981\u4f7f\u7528\u91d1\u5361
2. \u9078\u53d6\u524d\u4e00\u5929\u5df2\u7d93\u4f7f\u7528\u4e00\u5f35\u91d1\u5361\u6642\u7684\u91d1\u984d\u4e26\u6263\u6389\u4eca\u5929\u7684\u8ca0\u6578\u64da -> \u9019\u4ee3\u8868\u4e86\u6211\u5011\u8a8d\u70ba\u625b\u4f4f\u4eca\u5929\u7684\u8ca0\u6578\u64da\u6bd4\u8f03\u8cfa
\u90a3\u5f88\u660e\u986f\u9019\u6b21\u6211\u5011\u9078\u64c7\u4e86\u7b2c\u4e8c\u500b\u65b9\u6848\uff0c\u56e0\u70ba\u4e0a\u6b21\u82e5\u6c92\u6709\u4f7f\u7528\u91d1\u5361\uff0c\u90a3\u5c31\u7b97\u4eca\u5929\u4f7f\u7528\u91d1\u5361\u4e5f\u4f9d\u7136\u70ba0\uff1b\u53cd\u4e4b\u82e5\u6211\u5011\u9078\u64c7\u5728\u4e0a\u6b21\u4f7f\u7528\u91d1\u5361\uff0c\u800c\u4eca\u5929\u625b\u4f4f\u8ca0\u6578\u64da\u9084\u6703\u6709 4 \u7684\u6536\u76ca\uff0c\u6839\u64da\u4e0a\u8ff0\u53ef\u4ee5\u63a8\u8ad6\u51fa\u4e0b\u9762\u7684\u7a0b\u5f0f\u78bc\u3002<\/p>\n\n\n\n
recMatrix[i][1] = max(recMatrix[i][0], recMatrix[i][1] + numList[i])\n#recMatrix[i][0] \u4ee3\u8868\u524d\u5929\u6c92\u4f7f\u7528\u91d1\u5361\uff0c\u4eca\u5929\u4f7f\u7528\uff0c\u6240\u4ee5\u4e0d\u9700\u8981\u52a0\u4e0a\u4eca\u5929\u7684\u6578\u64da\n#recMatrix[i][1] + numList[i] \u4ee3\u8868\u524d\u5929\u4f7f\u7528\u4e86\u91d1\u5361\uff0c\u4eca\u5929\u4e0d\u80fd\u4f7f\u7528\uff0c\u6240\u4ee5\u8981\u52a0\u4e0a\u4eca\u5929\u7684\u6578\u64da<\/code><\/pre>\n\n\n\n\u90a3\u5176\u5be6\u662f\u5230\u5982\u4eca\u4e5f\u5df2\u7d93\u628a\u6240\u6709\u8a72\u601d\u8003\u7684\u6771\u897f\u601d\u8003\u5b8c\u7562\uff0c\u63a5\u8457\u53ea\u8981\u5efa\u7acb\u597d\u905e\u8ff4\u5f0f\u5373\u53ef\u3002\u4f46\u6211\u9084\u662f\u628a\u6574\u500b\u5716\u8868\u5217\u51fa\u4f86\u5427\u3002<\/p>\n\n\n\n![\"\"](\"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/\u6295\u8cc7\u904a\u62326.png?resize=914%2C1024&ssl=1\")
<\/figure>\n\n\n\n\u5217\u51fa\u5716\u8868\u9019\u5728\u8003\u8a66\u6642\u662f\u975e\u5e38\u6709\u7528\u7684\uff0c\u8003\u8a66\u6642\u9593\u9019\u9ebc\u591a\uff0c\u7d55\u5c0d\u53ef\u4ee5\u5f88\u60a0\u9592\u756b\u500b\u5716\u7684\u3002
\u597d\u4e86\u65e2\u7136\u5df2\u7d93\u5b8c\u6210\u7684\u8a71\uff0c\u6211\u5011\u5c31\u5217\u51fa\u7a0b\u5f0f\u78bc\u5427\uff01<\/p>\n\n\n\n
n,k = [int(i) for i in input().split()]\nnewNumList = [int(i) for i in input().split()]\nrecMatrix = [[0 for j in range(k+1)] for i in range(len(newNumList)+1)] #\u5efa\u7acb\u5132\u5b58\u7528\u7684\u77e9\u9663\n#\u4ee5\u4e0b\u7684\u89e3\u6cd5\u6539\u7de8\u81ea40%\u89e3\u6cd5\uff0c\u53ea\u4e0d\u904e\u628atotal\u7528\u6210\u77e9\u9663\u53bb\u9032\u884c\u7d71\u8a08\nmaxScore = 0\nfor i in range(len(newNumList)):\n recMatrix[i+1][0] = max(recMatrix[i][0],0) + newNumList[i] # 0\u5f35\u91d1\u5361\n # \u9019\u90e8\u5206\u4f60\u6703\u767c\u73fe\u5230\u820740%\u90e8\u5206\u4e00\u6a23\n for j in range(1,k+1):#1~K\u5f35\u91d1\u5361\n recMatrix[i+1][j] = max(recMatrix[i][j-1],recMatrix[i][j] + newNumList[i])\n #\u6bd4\u8f03\u7528\u4e86\u91d1\u5361(\u5de6\u908a)\u548c\u4e0d\u7528\u91d1\u5361(\u53f3\u908a)\u8ab0\u6bd4\u8f03\u5927\uff0c\u628a\u5927\u7684\u5b58\u4e0b\u4f86\n maxScore = max(recMatrix[i+1][k],maxScore) #\u6bd4\u8f03\u524d\u9762\u7684\u6700\u5927\u503c\u8ddf\u73fe\u5728\u7684\u6700\u5927\u503c\u8ab0\u5927\nprint(maxScore)<\/code><\/pre>\n\n\n\n\u82e5\u4e00\u822c\u7684\u72c0\u6cc1\u4e0b\u6211\u6703\u8aaa\u5df2\u7d93\u5b8c\u6210\u4e86\uff0c\u4f46APCS\u901a\u5e38\u5c0d\u65bcPython\u6703\u6bd4\u8f03\u56b4\u683c\uff0c\u56e0\u6b64\u7565\u70ba\u9032\u884c\u4e00\u4e9b\u6539\u826f\u3002
\u4ee5\u4e0b\u6539\u826f\u5169\u500b\u90e8\u5206
1. \u628a\u6240\u6709\u8ca0\u6578\u64da\u4e2d\u9593\u7684\u6b63\u6578\u64da\u5148\u52a0\u4e00\u8d77 -> \u56e0\u70ba\u91d1\u5361\u4e0d\u6703\u5f71\u97ff\u6b63\u6578\u64da\u7684\u8a08\u7b97
2. \u628a\u77e9\u9663\u8b8a\u6210\u5169\u500b\u6578\u5217\u76f8\u4e92\u4ea4\u63db -> \u56e0\u70ba\u66f4\u524d\u9762\u7684\u6578\u64da\u5df2\u7d93\u7528\u4e0d\u5230\u4e86\uff0c\u90a3\u4e0d\u5982\u91cb\u653e\u51fa\u4f86\u589e\u52a0\u8a08\u7b97\u6548\u80fd\u3002<\/p>\n\n\n\n
#Python\nn,k = [int(i) for i in input().split()]\nnumList = [int(i) for i in input().split()]\nnewNumList = []#\u70ba\u4e86\u6e1b\u5c11\u6642\u9593\u8907\u96dc\u5ea6\uff0c\u5148\u5e6b\u5fc5\u6b63\u7684\u90e8\u5206\u9032\u884c\u52a0\u7e3d\u8655\u7406\nt = 0\nfor i in range(n):\n if numList[i]<0:\n newNumList.append(t)\n newNumList.append(numList[i])\n t = 0\n else:\n t += numList[i]\nif t >=0:\n newNumList.append(t)\nrecList1,recList2 = [[0]*(k+1) for i in range(2)] #\u5efa\u7acb\u5132\u5b58\u7528\u7684\u77e9\u9663\n#\u4ee5\u5f80\u90fd\u6703\u7528\u4e00\u500b\u6eff\u7248\u7684 (k+1)^2\u77e9\u9663\uff0c\u4f46APCS\u5c0d\u65bcPython\u6bd4\u8f03\u56b4\u683c\uff0c\u6240\u4ee5\u9084\u662f\u7a0d\u5fae\u7bc0\u7701\u4e00\u9ede\u6703\u6bd4\u8f03\u597d\n#\u4ee5\u4e0b\u7684\u89e3\u6cd5\u6539\u7de8\u81ea40%\u89e3\u6cd5\uff0c\u53ea\u4e0d\u904e\u628atotal\u7528\u6210\u77e9\u9663\u53bb\u9032\u884c\u7d71\u8a08\nmaxScore = 0\nfor i in range(len(newNumList)):\n recList2[0] = max(recList1[0],0) + newNumList[i] # 0\u5f35\u91d1\u5361\n # \u9019\u90e8\u5206\u4f60\u6703\u767c\u73fe\u5230\u820740%\u90e8\u5206\u4e00\u6a23\n for j in range(1,k+1):#1~K\u5f35\u91d1\u5361\n recList2[j] = max(recList1[j-1],recList1[j] + newNumList[i])\n #\u6bd4\u8f03\u7528\u4e86\u91d1\u5361(\u5de6\u908a)\u548c\u4e0d\u7528\u91d1\u5361(\u53f3\u908a)\u8ab0\u6bd4\u8f03\u5927\uff0c\u628a\u5927\u7684\u5b58\u4e0b\u4f86\n maxScore = max(recList2[k],maxScore) #\u6bd4\u8f03\u524d\u9762\u7684\u6700\u5927\u503c\u8ddf\u73fe\u5728\u7684\u6700\u5927\u503c\u8ab0\u5927\n recList1,recList2 = recList2,recList1 #\u5c0d\u8abf\u6e96\u5099\u91cd\u505a\nprint(maxScore)<\/code><\/pre>\n\n\n\n\/\/C++\n#include <iostream>\n#include <vector>\n#include <algorithm>\n\nusing namespace std;\n\nint main() {\n int n, k;\n cin >> n >> k;\n vector<int> numList(n);\n for (int i = 0; i < n; ++i) {\n cin >> numList[i];\n }\n\n vector<int> newNumList;\n int t = 0;\n for (int i = 0; i < n; ++i) {\n if (numList[i] < 0) {\n if (t > 0) {\n newNumList.push_back(t);\n t = 0;\n }\n newNumList.push_back(numList[i]);\n } else {\n t += numList[i];\n }\n }\n if (t > 0) {\n newNumList.push_back(t);\n }\n\n vector<int> recList1(k+1, 0), recList2(k+1, 0);\n int maxScore = 0;\n for (int i = 0; i < newNumList.size(); ++i) {\n recList2[0] = max(recList1[0], 0) + newNumList[i];\n for (int j = 1; j <= k; ++j) {\n recList2[j] = max(recList1[j - 1], recList1[j] + newNumList[i]);\n }\n maxScore = max(recList2[k], maxScore);\n recList1.swap(recList2); \/\/ \u5c0d\u8abf\u4ee5\u9032\u884c\u4e0b\u4e00\u8f2a\u8fed\u4ee3\n }\n \n cout << maxScore << endl;\n return 0;\n}\n <\/code><\/pre>\n\n\n\n<\/p>\n","protected":false},"excerpt":{"rendered":"
\u9019\u6b21\u7684\u984c\u76ee\u8ddf\u904e\u5f80\u7684\u984c\u76ee\u96e3\u5ea6\u9032\u884c\u5c0d\u6bd4\u7684\u8a71\uff0c\u6703\u767c\u73fe\u96e3\u5ea6\u964d\u4f4e\u6eff\u591a\u7684\uff0c\u57fa\u672c\u4e0a\u53ea\u8981\u6709\u4e00\u5b9a\u7684\u4f5c\u984c\u91cf\uff0c\u9762\u5c0d\u984c\u76ee\u6642\u61c9\u8a72\u90fd\u6703\u6709\u4e9b\u60f3\u6cd5\u3002<\/p>\n","protected":false},"author":12,"featured_media":4158,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[1],"tags":[39,75,203,229,230,231,228,29,9,20,204,25],"blocksy_meta":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/i0.wp.com\/codingbar.ai\/content\/wp-content\/uploads\/2023\/11\/justtryit_coding_black_word_1920_x_740_faeab31e-983b-4925-8817-a03f70d8795d-1024x1024.jpg?fit=1024%2C1024&ssl=1","_links":{"self":[{"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/posts\/4085"}],"collection":[{"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/comments?post=4085"}],"version-history":[{"count":39,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/posts\/4085\/revisions"}],"predecessor-version":[{"id":4168,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/posts\/4085\/revisions\/4168"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/media\/4158"}],"wp:attachment":[{"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/media?parent=4085"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/categories?post=4085"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codingbar.ai\/content\/wp-json\/wp\/v2\/tags?post=4085"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}