$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;
}

二维费用 $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}。$$

#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; 
}