http://www.elijahqi.win/archives/3112 题目描述
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： 复制
4 1 2 2 3 输出样例#1： 复制
5 输入样例#2： 复制
4 1 1 2 3 输出样例#2： 复制
5 说明
数据范围 对于 30% 的数据，N ≤ 1000
对于 100% 的数据，N ≤ 10^5
真是sb 树状数组求dp都yy了很久 直接到这来做思维难度直线下降
考虑贪心的去构造方案 模拟nlog(n) 求最长上升子序列的方法 这时候如果a相同 那么我必然让他们的c的权值递降更好 这样显然会对我b的答案产生更多帮助所以就每次记录一下最后一次出现的位置 然后直接从0开始dfs一下即可 因为加边..的顺序是反的.. 然后就构造出了c 然后求最长下降子序列 用树状数组倒序求即可
#include<cstdio> #include<cctype> #include<algorithm> #define ll long long using namespace std; inline char gc(){ static char now[1<<16],*S,*T; if(S==T){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++; } inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f; } const int N=1e5+10; struct node{ int y,next; }data[N<<1]; int num,h[N],last[N],c[N],s[N],n;ll ans; inline void insert1(int x,int y){ data[++num].y=y;data[num].next=h[x];h[x]=num; } inline void dfs(int x){ c[x]=++num; for (int i=h[x];i;i=data[i].next) dfs(data[i].y); } inline void add(int x,int v){while(x<=n+1) s[x]=max(s[x],v),x+=x&-x;} inline int query(int x){static int tmp; tmp=0;while(x) tmp=max(tmp,s[x]),x-=x&-x;return tmp; } int main(){ //freopen("bzoj5158.in","r",stdin); n=read(); for (int i=1;i<=n;++i){ static int x;x=read(); insert1(last[x-1],i);last[x]=i; }num=-1;dfs(0); //for (int i=1;i<=n;++i) printf("%d ",c[i]); for (int i=n;i;--i){static int tmp; tmp=query(c[i])+1;ans+=tmp;add(c[i],tmp); } printf("%lld\n",ans); return 0; }