caioj 1063 动态规划入门（一维一边推1：美元和马克）

这道题一开始我是这么想的

最后的答案肯定是某次的马克换回来的，但这个该怎么确定？？

实际上应该把范围缩小，只看最后一次和倒数第二次之间有什么联系。

可以发现，只有两种可能，最后一天换或者不换。换的话就要求出

最后一天之前最多的马克，不换的话就是最后一天前最多的美元。

设d[i]为前i次最多的美元，m[i]为前i次最多的马克，x为今天换的值

那么可以得到

d[i] = max(d[i-1], m[i-1] * 100 / x)

m[i] = max(m[i-1], d[i-1] * x / 100)

最后d[n]就是答案

大致步骤

先尝试设立状态

然后判断当前状态可以由哪些状态推来，写转移方程

写出答案和起始条件

#include<cstdio>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112;

double d[MAXN], m[MAXN];

int n;

int main()

{

	double x;

	scanf("%d%lf", &n, &x);

	d[0] = 100;

	m[0] = x;

	REP(i, 1, n)

	{

		scanf("%lf", &x);

		d[i] = max(d[i-1], m[i-1] * 100 / x);

		m[i] = max(m[i-1], d[i-1] * x / 100);

	}

	printf("%.2lf\n", d[n-1]);

	return 0;

}

巴特西

caioj 1063 动态规划入门（一维一边推1：美元和马克）

最新文章

热门文章