[CSP-S模拟测试]:降雷皇（DP+树状数组）

题目描述

降雷皇哈蒙很喜欢雷电，他想找到神奇的电光。
哈蒙有$n$条导线排成一排，每条导线有一个电阻值，神奇的电光只能从一根导线传到电阻比它大的上面，而且必须从左边向右传导，当然导线不必是连续的。
哈蒙想知道电光最多能通过多少条导线，还想知道这样的方案有多少。

输入格式

第一行两个整数$n$和$type$。$type$表示数据类型

第二行$n$个整数表示电阻。

输出格式

第一行一个整数表示电光最多能通过多少条导线。
如果$type=1$则需要输出第二行，表示方案数，对$123456789$取模。

样例

样例输入：

5 1
1 3 2 5 4

样例输出：

3
4

数据范围与提示

对于$20\%$的数据，$n\leqslant 10$；

对于$40\%$的数据，$n\leqslant 1,000$；

对于另外$20\%$的数据，$type=0$；

对于另外$20\%$的数据保证最多能通过不超过$100$条导线；

对于$100\%$的数据$n\leqslant 100000$，电阻值不超过$100000$。

题解

不输出方案数就是一个普通的$LCS$。

最经典的做法就是用树状数组做到$\Theta(n\log n)$。

对于这道题，无非就是在树状数组统计时再加一个方案数即可。

时间复杂度：$\Theta(n\log n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

const int mod=123456789;

int n,type;

int a[100001];

int tr[500000],val[500000],maxn;

pair<int,int> ans;

int lowbit(int x){return x&-x;}

void add(int x,int w,int sz)

{

	for(int i=x;i<=500000;i+=lowbit(i))

	{

		if(w==val[i])tr[i]=(tr[i]+sz)%mod;

		else if(w>val[i]){tr[i]=sz;val[i]=w;}

	}

}

pair<int,int> ask(int x)

{

	pair<int,int> res=make_pair(0,0);

	for(int i=x;i;i-=lowbit(i))

		if(val[i]>res.first)res=make_pair(val[i],tr[i]);

		else if(val[i]==res.first)res.second=(res.second+tr[i])%mod;

	return res;

}

int main()

{

	scanf("%d%d",&n,&type);

	add(1,0,1);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&a[i]);a[i]+=2;

		ans=ask(a[i]-1);

		add(a[i],ans.first+1,ans.second);

		maxn=max(maxn,a[i]);

	}

	ans=ask(maxn);

	printf("%d\n",ans.first);

	if(type)printf("%d",ans.second);

	return 0;

}

rp++

巴特西