B - Adjacent Chmax

第一次自己写出$700700$分的题!!!

记录一下.

首先能到$ii$位置后面的一定是满足$ii$后面的连续的$maxmax$.这点很显然.

那么我们设置$dpdp$状态:

$f_{i,j}f\_\{i,j\}$为到了第$ii$个位置,值是$jj$的方案数.注意这是从$11$开始数到$ii$考虑本质不同的序列.同时考虑后面的影响.

初值就很显然,就是后面能到$11$的所有值设置成$11$.

那么其实就有$22$种情况.

第一种情况是前面的值比我现在要大,但是它和我之间有个更大的,这种是不能转移的,很显然这种维护一个单调栈即可,单调栈内都可以转移.

第二种情况后面的值能覆盖到我当前的位子.这种值也在$ii$位置是存在的也要考虑转移.

具体点如何考虑这两种转移呢?

其实假如在单调栈里面就是单调栈里面所有的方案数加起来转移到当前位子.

不在单调栈里面就要考虑两种情况了:

$1.1.$我能把前面值比我小的全部转移掉,因为前面小的不可能会是后面带来的贡献,$dpdp$是不能有后效性的.

$2.2.$我能把前面出现过的比我大的转移掉,换句话说在单调栈里面比我大的也能被我转移掉.

单调栈里面用个后缀优化即可.

至此$dpdp$就做完了,这个后效性好难考虑))

$code:code:$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=5005;
const int mod=998244353;

ll f[N][N];
ll suf[N][N];
ll sum[N][N];
ll res[N];
bool vis[N];
int a[N];
bool use[N][N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i];
	int mx=0;
	for(int i=1;i<=n;i++)
	{
		mx=max(mx,a[i]);
		f[1][mx]=1;
	}
	for(int i=1;i<=n;i++)
	{
		int mx=0;
		for(int j=i;j<=n;j++)
		{
			mx=max(mx,a[j]);
			use[i][mx]=true;
		}
	}
	vis[a[1]]=true;
	for(int i=n;i>=1;i--)
		if(vis[i])	suf[1][i]=(suf[1][i+1]+f[1][i])%mod;
		else		suf[1][i]=(suf[1][i+1]);
	for(int i=1;i<=n;i++)
	{
		sum[1][i]=(f[1][i]+sum[1][i-1])%mod;
	}
	stack<int>st;
	st.push(a[1]);
	res[a[1]]=f[1][a[1]];
	for(int i=2;i<=n;i++)
	{
		vis[a[i]]=true;
		while(st.size()&&a[i]>st.top())	vis[st.top()]=false,st.pop();
		st.push(a[i]);
		for(int j=a[i];j<=n;j++)
		{
			if(use[i][j])		f[i][j]=(sum[i-1][j]+suf[i-1][j+1])%mod;
			else if(vis[j])		f[i][j]=suf[i-1][j];
		}
		for(int j=a[i];j<=n;j++)
		{
			sum[i][j]=(sum[i][j-1]+f[i][j])%mod;
		}
		res[a[i]]=f[i][a[i]];
		for(int j=n;j>=1;j--)
			res[j]=f[i][j];
		for(int j=n;j>=1;j--)
		{
			if(vis[j])	suf[i][j]=(suf[i][j+1]+res[j])%mod;
			else		suf[i][j]=suf[i][j+1];
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++)
		ans+=f[n][i],ans%=mod;
	printf("%lld\n",ans);
	return 0;
}

最后提供$22$组有用的样例:

3
3 2 1
ans:5
4
4 3 2 1
ans:14