自动搬运

查看原文

来自洛谷，原作者为

	游戏的人 这个家伙太弱，什么也没有留下

搬运于2025-08-24 22:20:05，当前版本为作者最后更新于2020-04-12 11:04:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到题目觉得很有趣,就点进来看了题,很有意思的一道题。

思路

仔细审题，发现这个相邻数值间的比较有点像一个个正着的和反着的不降子序列。

于是猛地发现，可以先找出所有的不降子序列，再按照这个序列从低分到高分依次每个人多分发一个橘子（相同得分，分到橘子相同），最后再把橘子数相加，两个相反的不降子序列峰顶取最大值。

听不懂的可以看下图样例解释（图纯手画，大佬轻喷）

可以看到，3、4、5正着和反着有两个不降子序列，形成了一座类似山的模样，按照成绩高低，从得3分的人开始，从低分到高分，每个人发到的橘子加1（图中方块表示橘子数），可以发现答案不就是图中方块的总数吗？

这里再给出一组自制样例和解释图，可根据前文和代码理解。

11
3 6 9 4 7 7 2 13 15 15 19
输出：24

总结

• 读入，将初始每个人收到橘子数（即方块数）初始化为1。
• 求出正着所有不降子序列并依次把橘子数+1。
• 同上反着求。（这里遇到峰顶取最大值）
• 统计，输出。

AC代码

#include<iostream>
#include<cmath>
using namespace std;
int a[1000001],t[1000001],n,k;//a数组存分数，t数组是橘子数即方块数 
long long ans;//数值很大
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],t[i]=1;//读入，初始化 
	for(int i=2;i<=n;i++)//求正着的不降子序列
	{
		if(a[i-1]<a[i])t[i]=t[i-1]+1;//给橘子数赋值 
		if(a[i-1]==a[i])t[i]=t[i-1];//分数相同则与上个人相等 
	}
	for(int i=n;i>=2;i--)//求反着的不降子序列，并把峰顶的人分到橘子取更大值，其余同上 
	{
		if(a[i]<a[i-1])t[i-1]=max(t[i-1],t[i]+1); 
		if(a[i-1]==a[i])t[i-1]=t[i];
	}
	for(int i=1;i<=n;i++)ans+=t[i];//统计 
	cout<<ans;//输出 
}

完结撒花

改了很多次,辛苦管理员大大了,求过!!

大佬轻喷（留个赞吧）