1092: 最大价值(dollars) 算法 动态规划
题目地址：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
|
package com.daxin;
import java.util.Arrays;
import java.util.Scanner;
/** * Created by Daxin on 2017/8/20.
* 动态规划
*/
public class MaxDollarValue {
public static void main(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));
}
public static double getMaxValue(int[] nums) {
int len = nums.length;
double[][] table = new double[len][len + 1];//
table[0][1] = 1;
for (int i = 0; i < table.length; i++) {
table[i][0] = nums[i];
}
for (int i = 2; i < table[0].length; i++) {
for (int j = 1; j < table.length; j++) {
double noChange = table[j - 1][i - 1];
double change = noChange * nums[j - 1] * 1.0 / nums[j];
table[j][i] = noChange > change ? noChange : change;
}
}
for(double []ds :table){
System.out.println(Arrays.toString(ds));
}
return Math.floor(table[table.length - 1][table[0].length - 1] * 10000) / 100;
}
} |