100个动归方程：NOIP必备资源与策略解析

动归方程，即动态规划中的回溯法，是算法设计中一种解决复杂优化问题的重要技术，尤其在计算机竞赛如NOIP中占有核心地位。这里列出了100个动归方程示例，覆盖了多种常见的问题类型，包括资源分配、背包问题、线性动态规划、剖分问题、系统可靠性、贪心策略、树型动态规划以及计数问题等。 1. **机器分配问题**：该问题涉及到将机器分配给任务，通过F[I,j]:= max(f[i-1,k]+w[i,j-k])求解最优分配方案，其中w[i,j]代表机器i处理任务j的效率。 2. **01背包问题**：经典背包问题，F[I,j]表示前i个物品中选取重量不超过j的物品组合的最大价值，通过F[I,j]:= max(f[i-1,j-v]+w, f[i-1,j])来寻找最大收益。 3. **朴素最长非降子序列**：通过F:= max{f[j]+1}计算一个序列中连续且递增的子序列长度。 4. **石子合并与多边形剖分**：这两类问题是关于分割和优化，如F[i,j]:= min(f[i,k]+f[k+1,j]+sum[i,j])求解最小成本的石子合并操作，F[I,j]:= min(f[i,k]+f[k,j]+a[k]*a[j]*a)处理多边形剖分问题。 5. **乘积最大与系统可靠性**：前者涉及求解F[i,j]:= max(f[k,j-1]*mult[k,i])，后者是完全背包问题，F[i,j]:= max{f[i-1,j-c*k]*P[I,x]}，涉及概率和资源利用率。 6. **贪心动态规划**：如快餐问题和过河问题，分别通过不同的贪心策略求解最优化问题。 7. **多边形-讨论的动态规划**：F[i,j]考虑四种情况下的组合效果，通过g函数确定最优状态。 8. **树型动态规划**：加分二叉树模型F[I,j]:= max{f[I,k-1]*f[k+1,j]+c[k]}，选课问题中则用f[i,j]表示选j门课程的最大学分。 9. **计数问题**：如砝码称重和核电站问题，分别通过递推关系式解决，如f[f[0]+1]=f[j]+k*w[j]。 10. **最大子矩阵**：求解具有特定性质（如递增）的最大连续子矩阵。 这些动归方程涵盖了动态规划的多种应用领域，掌握它们对于理解算法思想、解决实际问题以及参加编程竞赛至关重要。在学习过程中，不仅需要理解和记忆这些公式，还要结合实例进行实践，逐步提高动态规划的运用能力。同时，注意观察问题的模式，学会抽象出通用的动态规划模板，这对提升编程技能和问题解决能力大有裨益。