【动态规划】在考研程序设计题中的评分要点
〈考研程序设计题评分标准〉对DP题要求：状态定义、转移方程、边界初始化、空间优化。常见题型：背包、最长公共子序列、编辑距离。
- 〈考研程序题评分标准〉强调状态定义必须无歧义，例如 dp[i][j] 表示前i个物品容量j的最大价值。
- 转移方程需体现最优子结构，如「0-1背包」dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])。
- 边界条件：dp[0][]=0，注意数组越界。
- 优化：滚动数组将空间从O(nW)降至O(W)。
// 考研程序设计题评分标准 - 0-1背包示例 (C++)
int knapsack(vector<int>& w, vector<int>& v, int W) {
int n = w.size();
vector<int> dp(W+1, 0);
for (int i = 0; i < n; i++)
for (int j = W; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
return dp[W];
}
评分员会检查是否遗漏了“每个物品只能用一次”的条件，以及是否正确处理了w[i]可能为0的情况。〈考研程序设计题评分标准〉中，DP题满分的关键在于边界与优化。
【图论算法】Dijkstra、Floyd 评分细则
〈考研程序题评分标准〉对图论题注重：算法正确性、复杂度、邻接表/邻接矩阵选择。常见失分：未处理负权边（Dijkstra不适用）。
- Dijkstra：使用优先队列优化，时间复杂度O((V+E)logV)。
- Floyd：三重循环，注意k在最外层，初始化INF。
- 〈考研程序题评分标准〉要求必须说明图存储方式，邻接表适合稀疏图。
// Dijkstra 优先队列实现 (考研评分标准推荐)
using P = pair<int,int>;
vector<int> dijkstra(vector<vector<P>>& g, int s) {
vector<int> dist(g.size(), 1e9);
priority_queue<P, vector<P>, greater<P>> pq;
dist[s]=0; pq.push({0,s});
while(!pq.empty()){
auto [d,u]=pq.top(); pq.pop();
if(d!=dist[u]) continue;
for(auto [v,w]:g[u]) if(dist[v]>dist[u]+w)
dist[v]=dist[u]+w, pq.push({dist[v],v});
}
return dist;
}
〈考研程序设计题评分标准〉强调：必须检查节点编号从0还是1开始，避免越界。另外，负权边需用SPFA或Bellman-Ford。
【代码规范】变量命名、注释与结构
〈考研程序题评分标准〉中代码规范占25%。命名清晰、缩进统一、避免冗余注释。下面给出正反示例。
// 不推荐 (扣分项)
int a[100][100]; int f(int x,int y){return x>y?x:y;}
// 推荐 (符合考研评分标准)
const int MAXN = 100;
int dp[MAXN][MAXN];
int max(int a, int b) { return a > b ? a : b; }
〈考研程序设计题评分标准〉建议：函数不超过50行，全局变量谨慎使用。注释应说明“为什么”而非“是什么”。
- 使用有意义的变量名：`maxProfit` 而非 `mp`。
- 每个函数前加简短功能描述。
- 〈考研程序题评分标准〉提倡模块化，主函数尽量简洁。
【调试与测试】边界覆盖与错误排查
〈考研程序设计题评分标准〉测试部分占15%。构造用例：正常、边界、异常。例如排序算法测试空数组、单元素、重复元素。
- 使用断言或简单print，但最终代码需删除调试输出。
- 〈考研程序题评分标准〉建议：先写测试用例再编码（测试驱动）。
- 常见错误：数组越界、整数溢出、除以零。
// 测试用例示例 (考研评分标准视角)
vector<int> test_cases = {5, 2, 9, 1, 5, 6};
sort(test_cases.begin(), test_cases.end());
// 验证有序
for (int i = 1; i < test_cases.size(); i++)
assert(test_cases[i] >= test_cases[i-1]);
〈考研程序设计题评分标准〉特别提醒：不要忽略输入规模为0的情况，很多考生因此失分。