poj1260Pearls(dp)

题目链接：http://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 }