poj1260Pearls动态规划问题如何解决？
- 内容介绍
- 文章标签
- 相关推荐
本文共计644个文字，预计阅读时间需要3分钟。
题目链接：http://poj.org/problem?id=1260
具体思路：首先，所需的珍珠数目是固定的，而每种珍珠所需数目，可以用较贵的珍珠替代。具体来说，可以用价格高的珍珠代替价格低的珍珠，直到满足所需数目为止。然后，题目所给珍珠的数目可以用来代替所需的珍珠数目。
题目链接：poj.org/problem?id=1260
具体思路：
首先，所需珍珠的数目是固定的，而且每种珍珠所需的数目，可以使用比此种珍珠珍贵(就是价格高的)的珍珠所替代，其次，题目所给珍珠的顺序是按价格由低到高给的，我们可以发现一个规律，珍珠不能隔着种类交换，就是说假设一共三类珍珠，第一种如果需要用第三种替代的话，那么第二种也必须被第三种替代，如果不这么做的话那么第二种需要单独支付额外费用，那么此时，显然如果把第一种用第二种替代更合适，花费更少。这只是说明了珍珠不能隔着替换。我们可以求前i种珍珠所花费的最少费用，那么第i种珍珠所花费的费用可以有多种选择，我们需要求出多种选择中所花费的最少的费用，我们可以用j来枚举前i种所有的选择，可以得到动态转移方程dp[i] = min(dp[i] , (sum[i] - sum[j]) * p[i] + dp[j]);值得注意的是，前i种珍珠的所有选择是从前i种全部都由第i种珍珠所替换枚举到前i种珍珠只有第i种珍珠是按照第i种珍珠价格购买的(也就是前i种没有一种被第i种替换)。
本文共计644个文字，预计阅读时间需要3分钟。
题目链接：http://poj.org/problem?id=1260
具体思路：首先，所需的珍珠数目是固定的，而每种珍珠所需数目，可以用较贵的珍珠替代。具体来说，可以用价格高的珍珠代替价格低的珍珠，直到满足所需数目为止。然后，题目所给珍珠的数目可以用来代替所需的珍珠数目。
题目链接：poj.org/problem?id=1260
具体思路：
首先，所需珍珠的数目是固定的，而且每种珍珠所需的数目，可以使用比此种珍珠珍贵(就是价格高的)的珍珠所替代，其次，题目所给珍珠的顺序是按价格由低到高给的，我们可以发现一个规律，珍珠不能隔着种类交换，就是说假设一共三类珍珠，第一种如果需要用第三种替代的话，那么第二种也必须被第三种替代，如果不这么做的话那么第二种需要单独支付额外费用，那么此时，显然如果把第一种用第二种替代更合适，花费更少。这只是说明了珍珠不能隔着替换。我们可以求前i种珍珠所花费的最少费用，那么第i种珍珠所花费的费用可以有多种选择，我们需要求出多种选择中所花费的最少的费用，我们可以用j来枚举前i种所有的选择，可以得到动态转移方程dp[i] = min(dp[i] , (sum[i] - sum[j]) * p[i] + dp[j]);值得注意的是，前i种珍珠的所有选择是从前i种全部都由第i种珍珠所替换枚举到前i种珍珠只有第i种珍珠是按照第i种珍珠价格购买的(也就是前i种没有一种被第i种替换)。