题目描述
applepi训练了一个可以自动在股票市场进行量化交易的模型。通常来说，applepi写出的模型，你懂得，就好比一架印钞机。不过为了谨慎起见，applepi还是想先检查一下模型的效果。
applpie收集了“塞帕思股份(surpass)”在最近的连续N天内的价格。在每一天中，他可以做如下事情之一：
1. 睡（把）觉（妹）。
2. 以当天的价格作为成交价买入1股“塞帕思”的股票。
3. 以当天的价格作为成交价卖出1股“塞帕思”的股票。
最初applepi不持有该股票。现在你需要计算出在最优策略下，N天后applepi能够获得的最大利润。
为了维护森林的和平，本着清仓甩锅的原则，在N天的交易结束后applepi也不能持有“塞帕思”的股票。
当然，成功购买某股票的前提是，applepi手中的钱数不少于该股票的价格，此外一直持有股票也是可以的。一开始applepi现在拥有的钱的数量为M
【输入格式】
每个测试点包含若干组数据，以EOF结尾。对于每组数据：
第一行1个整数N。
第二行N个正整数，相邻两个整数之间用1个空格隔开，表示每一天股票的价格。
【输出格式】
对于每组数据，首先按样例所示的格式“Case #k:”输出该组数据的编号，然后输出一个整数，表示applepi最大能够获得的利润。
【样例】
样例输入1
6 100
1 2 10 1 5 10
样例输出1
10000
【数据规模与约定】
对于50%的数据，1≤N≤1000。
对于100%的数据，1≤N≤100000，股票价格不超过100000，每个测试点至多包含5组数据。
题解
这道题，笔者一开始的想法是DP，但又发现好像写不出来，果断选择了用贪心做。
这道题的贪心思想就是：将股票价格分成不下降的若干段，在每段的开始买入，结束卖出。由于笔者能力有限，在此处便不予证明。
AC Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int n, m;
LL a[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
a[++ n] = -1;
LL ans = m;
int st = 1;
// ans 表示 现有钱数。
// st 表示 每段的开始
for (int i = 2; i <= n; i ++ )
if (a[i] < a[i - 1]) // 如果第i天不能接在上一段，则第i-1天就是上一段的结束。
{
ans = ans % a[st] + ans / a[st] * a[i - 1];
st = i;
}
printf("%lld\n", ans);
return 0;
}