题目来源：http://www.tyvj.cn:8080/Problem_Show.asp?id=1095

 

描述 Description

  在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元，使他从100美元开始，最后能获得最高可能的价值。

输入格式 Input Format

  输入文件的第一行是一个自然数N，1≤N≤100，表示戴维学习汇率的天数。

接下来的N行中每行是一个自然数A，1≤A≤1000。第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中，戴维既能用100美元买A马克也能用A马克购买100美元。

输出格式 Output Format

  输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元，保留两位小数)。

 

 

 

思路：

每一天所能拥有的最大的价值肯定要么是全马克，要么全是美元（不解释）

所以可以记录第i天所能拥有的最大马克数和美元数，来递推

 

ans[i][1]表示第i天所能拥有的最多的马克

ans[i][0]表示第i天所能拥有的最多的美元

 

自然

ans[i][1]=ans[i-1][1];

ans[i][1]=max(ans[j][0]*num[i]/100.0,ans[i][1]);//换成马克

ans[i][0]也同理

 

附上代码：

#include<stdio.h> #include<iostream> using namespace std; const int N=100; double ans[N+1][2];//0维表示美元 1维表示马克 double num[N+1];//num[i]的马克可以在第i天换100美元 int n; void input() {scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%lf",&num[i]);}return; } void prime() {ans[0][0]=100.0;for (int i=1;i<=n;i++){ans[i][0]=ans[i-1][0];ans[i][1]=ans[i-1][1];for (int j=1;j<i;j++){ans[i][0]=max(ans[j][1]/num[i]*100.0,ans[i][0]);//换成美元 }for (int j=0;j<i;j++){ans[i][1]=max(ans[j][0]*num[i]/100.0,ans[i][1]);//换成马克}}printf("%.2lf",ans[n][0]);return; } int main() {input();prime();return 0; } 

 

评测结果：

VijosNT Mini 2.0.5.6

#01: Accepted (0ms, 224KB)
#02: Accepted (0ms, 224KB)
#03: Accepted (0ms, 224KB)
#04: Accepted (0ms, 224KB)

Accepted / 100 / 0ms / 224KB