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

记录一下.

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

那么我们设置dpdp状态:

fi,jf_{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