题目描述
https://zoj.pintia.cn/problem-sets/91827364500/problems/91827365062
有n种珍珠，对于每种珍珠都必须要买a[i]个，单价为b[i]
n种珍珠的价格递增，可以用高价的珍珠替代低价的珍珠
每种珍珠在购买的时候必须多买十个
简单dp复习
Solution
首先在高价替代低价的时候，我们肯定用目前买的高价中价最低的
那么很容易得到dp的式子
我们用f[i][j]表示后i种珍珠，最后一个买的是j
然后就可以愉快的dp了
时间复杂度为 $O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <iostream>
#include <cstdio>
#define maxn 110
#define INF 1000000000
using namespace std;
int t, n;
int a[maxn], b[maxn];
int f[maxn][maxn];
void work() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
f[n][n] = (a[n] + 10) * b[n];
for (int i = n - 1; i; --i) {
f[i][i] = INF;
for (int j = i + 1; j <= n; ++j) {
f[i][j] = f[i + 1][j] + a[i] * b[j];
f[i][i] = min(f[i][i], f[i + 1][j]);
}
f[i][i] += (a[i] + 10) * b[i];
}
int ans = INF;
for (int i = 1; i <= n; ++i) ans = min(ans, f[1][i]);
cout << ans << endl;
}
int main() {
cin >> t;
while (t--) work();
return 0;
}
|