动态规划应用详解：资源分配与剖分问题

"本文介绍了十四个不同的动态规划问题及其对应的转移方程，涵盖了资源分配、01背包、最长非降子序列、石子合并、多边形剖分、系统可靠性、快餐问题、过河问题、多边形讨论、加分二叉树、选课问题以及砝码称重等经典动态规划应用。这些案例对于ACMER和OIer在提升动态规划能力方面非常有帮助。" 动态规划是一种通过将复杂问题分解成子问题来求解的方法，它通常涉及到建立一个状态空间，并定义一个状态到状态的转移过程。以下是对给定内容中各个动态规划问题的详细解释： 1. 机器分配问题：这是一个资源分配问题，F[I,j]表示在前i台机器上分配j单位资源的最大价值，转移方程是F[I,j]=max(f[i-1,k]+w[i,j-k])。 2. 01背包问题：F[I,j]表示在前i个物品中选择总重量不超过j的物品的最大价值，转移方程是F[I,j]=max(f[i-1,j-v[i]]+w[i],f[i-1,j])。 3. 最长非降子序列：F[i]表示序列中以第i个元素结尾的最长非降子序列的长度，转移方程是F[i]=max{f[j]+1}。 4. 石子合并：F[i,j]表示将区间[i, j]内的石子合并后的最小操作次数，转移方程是F[i,j]=min(f[i,k]+f[k+1,j]+sum[i,j])。 5. 多边形剖分：F[I,j]表示将多边形剖分为两个部分，使得i和j作为边界点时的最小面积，转移方程是F[I,j]=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i])。 6. 乘积最大：f[i,j]表示在区间[i, j]内找到分割点k，使得左右两部分乘积最大，转移方程是f[i,j]=max(f[k,j-1]*mult[k,i])。 7. 系统可靠性（完全背包）：F[i,j]表示在i个组件中，每个组件可以选择0个或多个，使得系统可靠性达到j的概率，转移方程是F[i,j]=max{f[i-1,j-c[i]*k]*P[I,x]}。 8. 快餐问题：F[i,j,k]表示前i条生产线可以生产出j个汉堡，k个薯条，且能生产的最多饮料数量，转移方程是F[i,j,k]=max{f[i-1,j',k']+(T[i]-(j-j')*p1-(k-k')*p2)divp3}。 9. 过河问题：f[i]表示到达第i个位置的最小代价，如果第i个位置有石头，则加上1，转移方程是f[i]=min{{f(i-k)}(notstone[i]), {f(i-k)}+1}(stone[i])。 10. 多边形讨论的动态规划：F[i,j]表示在多边形中找到分割点k，使得分割后两部分满足特定条件的最大价值，转移方程是F[i,j]=max{正正f[I,k]*f[k+1,j]; 负负g[I,k]*f[k+1,j]; 正负g[I,k]*f[k+1,j]; 负正f[I,k]*g[k+1,j];}，其中g为min。 11. 加分二叉树：F[I,j]表示在二叉树中，从左子节点到右子节点的路径上，选择节点i使得得分最大的值，转移方程是F[I,j]=max{f[I,k-1]*f[k+1,j]+c[k]}。 12. 选课问题：F[I,j]表示在以i为根节点的多叉树中，选择j门课程的最大学分，转移方程是f[i,j]=max{f[t[i].l,k]+f[t[i].r,j-k-1]+c[i]}。 13. 计数问题：例如砝码称重问题，使用一组砝码在天平上称出n种重量，转移方程未给出，但通常涉及组合优化和计数策略。 这些动态规划问题展示了动态规划在解决实际问题中的广泛适用性，理解并掌握这些转移方程有助于在面对复杂问题时构建有效的解决方案。