题目描述

Alice和Bob发明了一个新的游戏。给定一个序列{x0,x1,…,xn-1}。Alice得到一个序列{a0,a1,…,an-1},其中a;表示以x;结尾的最长上升子序列的长度;Bob得到一个序列{b0,b1,…,bn-1},其中bi表示以xi开头的最长下降子序列的长度。 Alice的得分是序列{a0,a1,…,an-1}的和,Bob的得分是{b0,b1,…,bn-1}的和。

输入输出格式

输入格式:

输入的第一行是n,第二行是序列{a0,a1,……’,an-1}。数据保证序列a可以由至少一个1到n的排列得到

输出格式:

输出包含一行,表示Bob能得到的最高分数

输入输出样例

输入样例#1: 复制
输出样例#1: 复制
输入样例#2: 复制
输出样例#2: 复制

说明

数据范围

对于 30% 的数据,N ≤ 1000

对于 100% 的数据,N ≤ 10^5

真是sb 树状数组求dp都yy了很久 直接到这来做思维难度直线下降

考虑贪心的去构造方案 模拟nlog(n) 求最长上升子序列的方法 这时候如果a相同 那么我必然让他们的c的权值递降更好 这样显然会对我b的答案产生更多帮助所以就每次记录一下最后一次出现的位置 然后直接从0开始dfs一下即可 因为加边..的顺序是反的.. 然后就构造出了c  然后求最长下降子序列 用树状数组倒序求即可

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论