1092: 最大价值(dollars) 算法 动态规划

标签：createcinblescanpackage算法自然数outrgs

题目地址：http://www.hustoj.com/oj/problem.php?id=1092

题目描述

Dave以某种方法获取了未来几天美元对德国马克的兑换率。现在Dave只有100美元，请编程序，使Dave通过几天的美元与德国马克的兑换后能得到最多的美元。

输入

第1行包含一个自然数n(l≤n≤I00)，表示Dave所知道的兑换率的天数。后面跟着n个自然数A (100≤A≤I000)。第i+l行的数A表示第i天的兑换率。它告诉那天他能用100美元购买A马克，或用A马克购买100美元。

输出

只有1行，输出Dave经过n天的兑换后能得到的最多的美元值。结果保留两位小数。注意不一定每天都需要兑换。说明：由于实数运算存在误差，结果在0.05的误差范围内将被认为是正确的。

样例输入
3
100
150
200
5
400
300
500
300
250

样例输出
200.00 //用力错误，正常输出应该是100
266.66

提示

样例2说明：第一天：100美元换成400德国马克第二天：400德国马克换成133.3333美元第三天：133.3333美元换成666.6666德国马克第四天：不换第五天：666.6666德国马克换成266.6666美元

解题思路：

使用动态规划记录每一天的历史的最大价值，然后最后根据历史价值求解！

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

packagecom.daxin;
importjava.util.Arrays;
importjava.util.Scanner;
/**
* Created by Daxin on 2017/8/20.
* 动态规划
*/
publicclassMaxDollarValue {
publicstaticvoidmain(String[] args) {
// Scanner cin = new Scanner(System.in);
// int n = cin.nextInt();
//
// int[] nums = new int[n];
//
// for (int i = 0; i < n; i++) {
// nums[i] = cin.nextInt();
// }
int[] nums = {400,300,500,300,250};
// int[] nums2 = {100, 150, 200};
// System.out.println(getMaxValue(nums1));
System.out.println(getMaxValue(nums));
}
publicstaticdoublegetMaxValue(int[] nums) {
intlen = nums.length;
double[][] table =newdouble[len][len +1];//
table[0][1] =1;
for(inti =0; i < table.length; i++) {
table[i][0] = nums[i];
}
for(inti =2; i < table[0].length; i++) {