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种替换)。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<map> 6 #include<queue> 7 #include<set> 8 #include<cmath> 9 #include<list> 10 #include<cstring> 11 #include<string> 12 #define ll long long 13 #define ull unsigned long long 14 #define inf 0x3f3f3f3f 15 #define inff 0x7fffffff 16 using namespace std; 17 const int N = 100 + 10; 18 19 int a[N], sum[N], dp[N], p[N]; 20 21 int main() { 22 23 int T; 24 cin >> T; 25 while (T--) { 26 memset(dp, 0x3f, sizeof(dp)); 27 int n; 28 cin >> n; 29 for (int i = 1; i <= n; i++) { 30 cin >> a[i] >> p[i]; 31 sum[i] = sum[i - 1] + a[i]; 32 } 33 dp[0] = 0; 34 for (int i = 1; i <= n; i++) { 35 for (int j = 0; j < i; j++) { 36 dp[i] = min(dp[i], (sum[i] - sum[j] + 10) * p[i] + dp[j]); 37 } 38 } 39 cout << dp[n] << "\n"; 40 } 41 42 return 0; 43 }
永远热爱，永远向着光。本文共计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种替换)。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<map> 6 #include<queue> 7 #include<set> 8 #include<cmath> 9 #include<list> 10 #include<cstring> 11 #include<string> 12 #define ll long long 13 #define ull unsigned long long 14 #define inf 0x3f3f3f3f 15 #define inff 0x7fffffff 16 using namespace std; 17 const int N = 100 + 10; 18 19 int a[N], sum[N], dp[N], p[N]; 20 21 int main() { 22 23 int T; 24 cin >> T; 25 while (T--) { 26 memset(dp, 0x3f, sizeof(dp)); 27 int n; 28 cin >> n; 29 for (int i = 1; i <= n; i++) { 30 cin >> a[i] >> p[i]; 31 sum[i] = sum[i - 1] + a[i]; 32 } 33 dp[0] = 0; 34 for (int i = 1; i <= n; i++) { 35 for (int j = 0; j < i; j++) { 36 dp[i] = min(dp[i], (sum[i] - sum[j] + 10) * p[i] + dp[j]); 37 } 38 } 39 cout << dp[n] << "\n"; 40 } 41 42 return 0; 43 }
永远热爱，永远向着光。