二维费用 $dp$ 入门题。

用 $dp_{0,i}$ 表示第 $i$ 天马克的最大值，$dp_{1,i}$ 表示第 $i$ 天美元的最大值。很明显，$dp_{0,0} = 100$。

于是可以列出如下状态转移方程：

$$dp_{0,i} = \max(dp_{0,i-1},\frac{dp_{1,i-1}}{100.0}\times a_i $$$$dp_{1,i} = \max(dp_{1,i-1},\frac{dp_{0,i-1}}{a_i}\times 100) $$$$最终答案即为\ dp_{1,n}。$$

$dp$

#include<bits/stdc++.h>
using namespace std;
int n,i,j,a;
double f[1005][3];
int main()
{
    cin>>n;
	f[1][1]=100;
	for(i=1;i<=n;i++)
	{
        cin>>a;
		if(i<2)f[1][2]=a;
		else{
			f[i][1]=max(f[i-1][1],f[i-1][2]*100.0/a);
			f[i][2]=max(f[i-1][2],f[i-1][1]/100.0*a)；
		}
	}
	printf("%.2lf",max(f[n][1],f[n][2]/a*100.0));
	return 0;
}

using namespace std;
double a[1010],t=100;
inline int read()
{
	register int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')w=-1;ch=getchar();
	}
	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
	return s*w;
}
inline void print(int x)
{
	if(x<0){
		putchar('-');
		x-=x;
	}
	if(x>9)print(x/10);
	putchar(x%10+'0');
}
int main() 
{
	//freopen("dollars.in","r",stdin);
	//freopen("dollars.out","w",stdout);
	int n;
    n=read();
    for (int i=1;i<=n;i++)
	{
         a[i]=read();
         a[i]/=100;
    }
    for (int i=1;i<=n;i++)
    {
      if (a[i]<a[i-1]) 
      {
      	t*=a[i-1]/a[i];
		}
	}
    printf ("%.2lf",t);
    return 0; 
}

$DP$ 入门题

状态定义：

由题目两种钱币可想到可以设两种状态：

$dp[i][0],dp[i][1]$

所以由此定义：

$dp[i][0]：第 i 天换过后可拥有的最大美元$

$dp[i][1]：第 i 天换过后可拥有的最大马克$

初始状态：

$dp[0][0]=100(初始有100美元)$

转移方程：

美元：

1.保留不兑换：$dp[i][0]=dp[i-1][0]$

2.由上一天兑换：$dp[i][0]=dp[i-1][1]/a[i]*100$

马克同理：

1.保留不兑换：$dp[i][1]=dp[i-1][1]$

2.由上一天兑换：$dp[i][1]=dp[i-1][0]/100*a[i]$

最终答案：

$dp[n][0]$（最后要都兑换成美元，注意输出保留两位小数（我还想着精度更高保留三位小数错了，并且是0 Wrong Answer，坑挺多的...））

#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n;
int a[105];
double dp[105][2];
signed main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	dp[0][0]=100;
	for(int i=1;i<=n;i++){
		dp[i][0]=max(dp[i-1][0],dp[i-1][1]/a[i]*1.000000*100);
		dp[i][1]=max(dp[i-1][1],dp[i-1][0]/100*a[i]*1.000000);
	}
	printf("%.2lf",dp[n][0]);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n;
double a[101];
int main() {
    scanf ("%d",&n);
    for (int i=1;i<=n;i++) {
         scanf ("%lf",&a[i]);
         a[i]/=100.0;
    }
    double now=100;
    for (int i=1;i<=n;i++)
      if (a[i]<a[i-1]) 
        now*=a[i-1]/a[i];    
    printf ("%.2lf",now);
    return 0; 
}