华师一附中OI组

标题: 题解（滚动数组优化版） [打印本页]
作者: gym123456    时间: 2021-10-15 19:31
标题: 题解（滚动数组优化版）
#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    时间: 2021-10-15 19:35
#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    时间: 2021-10-15 20:28
题目背景
此处省略maxint+1个数

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

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

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

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

注意：考虑到实数算术运算中进位的误差，结果在正确结果0.05美元范围内的被认为是正确的，戴维必须在最后一天结束之前将他的钱都换成美元。
作者: gym123456    时间: 2021-10-15 20:32
首先，对于每一天来讲，有四种可能：
1.美元转马克
2.马克转美元
3.现为美元不转
4.现为马克不转
所以当天最大的美元数等于max（昨天的美元数，昨天的马克数转美元）
最大马克数=max（昨天的马克数，昨天的美元数转马克）
第0天最大马克数为0，最大美元数为1
作者: gym123456    时间: 2021-10-15 20:36
于是乎，转态转移方程就出来了
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    时间: 2021-10-15 20:39
所以正解就出来了？
时间复杂度o(n),空间复杂度o(n)
观察状态转移方程
dp[i]只与dp[i-1]有关
考虑滚动数组优化
作者: gym123456    时间: 2021-10-15 20:46
//然后看到了洛谷最优解比我快
发现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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2