题解：P13095 炒股高手

题目：

对于每一份“鸡债” 计算其在

[s_{i},t_{i}]

内最大收益。

思路：

由于我们可以无限次的买卖，所以就可贪心一下，最优策略是在每一个价格上升的相邻两天（即

a_{i}<a_{i+1}

）进行买入和卖出。

这样，总收益倍数等于所有上升段的收益倍数的乘积。这样对于对对数就是直接相加减（对数运算：底数相乘等于指数相加）。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline void read(int &a){
	char ch;int f=1,k=0;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
	a=k*f;
}
int a[N],pre[N],n,m,k,s[N],t[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	read(n),read(m);
	for(int i=1;i<=n;i++){
		read(a[i]);
		pre[i]=pre[i-1];
		if(i>=2 and a[i]>a[i-1])
			pre[i]+=a[i]-a[i-1];
	}
	read(k);
	for(int i=1;i<=m;i++){
		read(s[i]),read(t[i]);
		cout<<k+pre[t[i]]-pre[s[i]]<<"\n";
	}
	return 0;
}

题解到此就结束了！祝各位 OIer 学有所成。

题解：P13095 炒股高手

文章操作

题目：

思路：

Code

相关推荐

评论

题解：P13095 炒股高手