題目鏈接：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 }
永遠熱愛，永遠向著光，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/455606.html
標籤：其他
上一篇：Docker快速入門(上)
下一篇：記一節有關密碼學承諾的課