题解（滚动数组优化版）

gym123456

#include <bits/stdc++.h>
using namespace std;
double dp[2][2];//虽然没必要，但万一毒瘤出题人把内存改为4mb呢？（doge）
int n,a;
inline int read(){
        int x=0;char ch=getchar();
        while(ch<'0'||ch>'9') ch=getchar();
        while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
        return x;
}
int main(){
        n=read();
        dp[0][1]=100;
        for(int i=1;i<=n;++i){
                a=read();
                dp[1][1]=max(dp[0][1],dp[0][0]*100.0/a);
                dp[1][0]=max(dp[0][0],dp[0][1]*a/100.0);
                dp[0][0]=dp[1][0];
                dp[0][1]=dp[1][1];
        }
        printf("%.2f",dp[0][1]);
        return 0;
}

gym123456

#include <stdio.h>
double dp[2][2];//虽然没必要，但万一毒瘤出题人把内存改为4mb呢？（doge）
int n,a;
int read(){
        int x=0;char ch=getchar();
        while(ch<'0'||ch>'9') ch=getchar();
        while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
        return x;
}
double mx(double x,double y){
        return x>y?x:y;
}
int main(){
        n=read();
        dp[0][1]=100;
        for(int i=1;i<=n;++i){
                a=read();
                dp[1][1]=mx(dp[0][1],dp[0][0]*100.0/a);
                dp[1][0]=mx(dp[0][0],dp[0][1]*a/100.0);
                dp[0][0]=dp[1][0];
                dp[0][1]=dp[1][1];
        }
        printf("%.2f",dp[0][1]);
        return 0;
}

gym123456

题目背景
此处省略maxint+1个数

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

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

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

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

注意：考虑到实数算术运算中进位的误差，结果在正确结果0.05美元范围内的被认为是正确的，戴维必须在最后一天结束之前将他的钱都换成美元。

gym123456

首先，对于每一天来讲，有四种可能：
1.美元转马克
2.马克转美元
3.现为美元不转
4.现为马克不转
所以当天最大的美元数等于max（昨天的美元数，昨天的马克数转美元）
最大马克数=max（昨天的马克数，昨天的美元数转马克）
第0天最大马克数为0，最大美元数为1

gym123456

于是乎，转态转移方程就出来了
a[i]=第i天的汇率
dp1[i]=第i天最大美元数
dp2[i]=第i天最大马克数
dp1[i]=max(dp1[i-1],dp2[i-1]*100.0/a[i])
dp2[i]=max(dp2[i-1],dp1[i-1]*a[i]/100.0)

gym123456

所以正解就出来了？
时间复杂度o(n),空间复杂度o(n)
观察状态转移方程
dp[i]只与dp[i-1]有关
考虑滚动数组优化

gym123456

//然后看到了洛谷最优解比我快
发现a也没有必要
于是直接卡到最优解

1. #include <stdio.h>
   
2. double dp[2][2];//虽然没必要，但万一毒瘤出题人把内存改为4mb呢？（doge）
   
3. int n,a;
   
4. int read(){//快读（没必要）
   
5.         int x=0;char ch=getchar();
   
6.         while(ch<'0'||ch>'9') ch=getchar();
   
7.         while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
   
8.         return x;
   
9. }
   
10. double mx(double x,double y){
    
11.         return x>y?x:y;//double的max建议手写
    
12. }
    
13. int main(){
    
14.         n=read();
    
15.         dp[0][1]=100;
    
16.         for(int i=1;i<=n;++i){
    
17.                 a=read();
    
18.                 dp[1][1]=mx(dp[0][1],dp[0][0]*100.0/a/*mark->dollar*/);//状态转移方程
    
19.                 dp[1][0]=mx(dp[0][0],dp[0][1]*a/100.0/*dollar->mark*/);
    
20.                 dp[0][0]=dp[1][0];
    
21.                 dp[0][1]=dp[1][1];//滚动数组
    
22.         }
    
23.         printf("%.2f",dp[0][1]);//保险起见可以恶心一点
    
24.         /*
    
25.         int ans=int(dp[0][1]*100);
    
26.         int ans1=ans%100;
    
27.         ans/=100;
    
28.         cout<<ans<<"."<<ans1;
    
29.         */
    
30.         return 0;
    
31. }

复制代码