首先证明最优解中肯定不会有交叉的替换，即在质量为a<b<j<c<d的情况下，如果a被c替换，那么b也一定要被c替换 假设在最优解中存在:a被c替换且b不被c替换的情况：
1.b不被任何替换 那么此时把a换成用b替换 得到比原来更优的解，错误
2.b被j替换，此时把a换成用j替换 得到比原来更优的解，错误
3.b被d替换,此时把b换成用c替换 得到比原来更优的解，错误
因此，不存在交叉的替换,那么最优解分为下面两种情况：
1.不存在断点，即所有的都用最大一种替换,dp[c]=(a[1]+...+a[c]+10)*p[c]
2.存在断点，最后一个断点为i,那么最优解必为dp[i]+(a[i+1]+..+a[c]+10)*p[c]
每个点都有可能是最后一个断点，因此产生了我们的DP方程:
dp[i]=min(dp[j]+(a[j+1]+..+a[i]+10)*p[i]）
把dp[0]设成0的话 2就包含了1 dp[c]就是最后的答案

• Re:我来发个容易理解的动规证明吧 (450) 1011051119 2011-12-04 11:26:27