做一套公司网站费用,驻马店专业做网站公司,公司做网站能抵扣进项税吗,免费ppt模板素材免费下载传送门 我在下面哦~~ Im here 思路 这是一道比较简单的DP题 美元可由马克转化得到#xff0c;马克可由美元转化得到#xff0c;最后要求最大的美元值 我们可以用f数组来记录最大能达到多少马克和多少美元。 定义一个\(f[N][3]\)的数组#xff0c;第一维表示到达了第i天 \(f[…传送门 我在下面哦~~ Im here 思路 这是一道比较简单的DP题 美元可由马克转化得到马克可由美元转化得到最后要求最大的美元值 我们可以用f数组来记录最大能达到多少马克和多少美元。 定义一个\(f[N][3]\)的数组第一维表示到达了第i天 \(f[i][1]\)表示到第i天能得到的最大美元值 \(f[i][2]\)表示到第i天能得到的最大马克值 每天有两种选择的方式 转化成另一种货币不转化成另一种货币这样就可以得出状态转移方程 \[f[i][1]max(f[i-1][1],f[i-1][2]/w[i]*100.000)\] \[f[i][2]max(f[i-1][2],f[i-1][1]*w[i]/100.000)\] 100.000是为了保证精度 代码 #includebits/stdc.h
#define N 110
using namespace std;double f[N][3],w[N];
int n;int main(){scanf(%d,n);for(int i1;in;i){scanf(%lf,w[i]);}f[1][1]100;f[1][2]w[1];for(int i2;in;i){f[i][1]max(f[i-1][1],f[i-1][2]/w[i]*100.000);f[i][2]max(f[i-1][2],f[i-1][1]*w[i]/100.000);}printf(%.2lf,max(f[n][1],f[n][2]/w[n]*100.000));return 0;
} 优化 我们可以发现第一维没有什么用所以我在上面的解释也不能明确的解释出它的作用因此我们可以把第一维删除只使用2个值状态转移方程如下 \[ f[1]max(f[1],f[2]/w[i]*100.000)\] \[f[2]max(f[2],f[1]*w[i]/100.000)\] #includebits/stdc.h
#define N 110
using namespace std;double f[3],w[N];
int n;int main(){scanf(%d,n);for(int i1;in;i){scanf(%lf,w[i]);}f[1]100;for(int i1;in;i){double xf[1];//如果下面使用f[1]有可能f[1]的值早已改变所以定义一个x,保证在使用的时候x的值没有改变f[1]max(f[1],f[2]/w[i]*100.000);f[2]max(f[2],x*w[i]/100.000);}printf(%.2lf,f[1]);return 0;
} 转载于:https://www.cnblogs.com/Snowindira/p/10836536.html