题解 P6364 【1024 程序员节发橙子】

· · 题解

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

思路

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

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

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

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

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

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

总结

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;//输出 
}

完结撒花

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

大佬轻喷（留个赞吧）