本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-07 15:31:25

这是一个环形问题

方法一 dp

一般的环形问题是断环为链，扩展为2倍长度。这个问题回到尾部后还有看能否和断点连接。所以我们可以直接枚举起点。当然还是扩展一倍长度，直接用%n确定点的位置。 我们设$a$数组为可以填数值的最大值，$a_i=min(b_{i-1},b_i,b_{i+1})$。

我们设$f_{ixy}$为$i$位置的数为$y$，$i-1$位置的数为$x$。 每个状态只与其前两个位置相关。 枚举起点状态的时间复杂度为$o(max(b_i)^2)$。 确定起始状态后，进行每个结点需要$o(N*max(b_i)^3)$，枚举3个结点的状态进行转移。

初始状态01位置还不能确定，从2位置开始确定1位置的。 对每个结点来说，如果前两个结点已经确定最大值，当前结点可以任意填数。 否则当前结点只能填确定的最大值。 结束后确定了n-2位置的，把环折回来再看n-1和0状态是否合法。最后仅把合法状态计入答案。

时间复杂度分析

因此总的时间复杂度为$o(N*max(b_i)^5)$.

#include<bits\/stdc++.h>
using namespace std;
const int N=2029;
typedef long long ll;
const ll mod=1e9+7;
int n,a[N],b[N],c[N];\/\/有几个连续的。
ll f[N][11][11],ans=0ll;\/\/当前状态可以与前面两个位置的状态相关。 

ll dp(int x,int y){
	\/\/01起点确定，从2开始，再回到01判断。

	memset(f,0,sizeof(f));
	f[1][x][y]=1;
	for(int i=2;i<n;i++){
		for(int j=a[i];j>=0;j--)
			for(int k=a[i-1];k>=0;k--){
				for(int l=a[i-2];l>=0;l--){
					if(max(l,k)==b[i-1])f[i][k][j]=(f[i][k][j]+f[i-1][l][k])%mod;
					else if(j==b[i-1])f[i][k][j]=(f[i][k][j]+f[i-1][l][k])%mod;
						else break;
				}		
			}
	}
	\/\/判断 n-2 n-1，x y  决定的n-1,0 
	\/\/
	ll ans=0;
	for(int i=a[n-1];i>=0;i--)
		for(int j=a[n-2];j>=0;j--){
			if(max(max(i,j),x)==b[n-1]&&max(max(i,x),y)==b[0]){
				ans=(ans+f[n-1][j][i])%mod;
			}
		}
	return ans ;
}

int main(){

	cin>>n;
	for(int i=0;i<n;i++){
		cin>>b[i];
		b[i+n]=b[i];
	}
	for(int i=0;i<n;i++){
		a[i]=min(min(b[(i+n-1)%n],b[i]),b[(i+1+n)%n]),a[i+n]=a[n];
	}
	ans=0;
	for(int i=a[0];i>=0;i--){
		for(int j=a[1];j>=0;j--){
			ll tmp=dp(i,j);
			ans=(ans+tmp)%mod;
		}
	}
	cout<<ans<<endl;
} 

方法二

根据b数值的情况，手工做几组样例我们可以发现：

当$b_i!=b_{i+1}$时候

如果$b_i>b_{i+1}$,那么我们可以唯一确定$i-1$的值为$b_i$.

如果$b_i<c_{i+1}$,那么我们可以唯一确定$i+2$的值为$b_i$.

我们设$a$数组为可以填数值的最大值，$a_i=min(b_{i-1},b_i,b_{i+1})$。 设$c$数组为数组可以确定填上的数值。

现在$c$内连续空着的数值其$a_i$是相当的。设其连续长度为$len$

• $len<=2$,相邻数填了，方案数为$(a_i+1)^{len}$
• $len>=3$,那每3个数至少一个填$a_i$

统计出连续长度后，我们可以设$f_{i0/1}$代表当前填数是否为$t=a_i$,然后用动态规划转移。

f[i][1]=(f[i-1][0]+f[i-1][1]);

f[i][0]=(f[i-1][1]t+f[i-2][1]t*t);

特殊情况，所有的$b_i$都相等

这时，就在一个环形区域内填数，每3个数至少有一个$b_i$,初始状态与线性稍微不同，进行特殊处理，头尾合起来时候用容斥减去不合法数据。

复杂度分析

这个算法不依赖$b_i$的大小，过程都是线性的，时间复杂度为$O(N)$。

#include<bits\/stdc++.h>
using namespace std;
const int N=2029;
typedef long long ll;
const ll mod=1e9+7;
int n,a[N],b[N],c[N],rk[N];\/\/有几个连续的。
ll f[N][2],ans=1ll;
ll work(int len,int t){\/\/环的情况：连续长度未len，最大数为t, 
	if(len==1)return 1ll;
	if(len==2)return ((t+1)*(t+1) )-1;
	for(int i=0;i<=len;i++)f[i][0]=f[i][1]=0;
	f[0][0]=t,f[0][1]=1;
	f[1][0]=(t+1)*t;
	f[1][1]=t+1;
	for(int i=2;i<len;i++){
		f[i][1]=(f[i-1][0]+f[i-1][1])%mod;
		f[i][0]=(f[i-1][1]*t+f[i-2][1]*t*t)%mod;
	} 
	return (f[len-1][0]+f[len-1][1])%mod;
} 
ll work2(int len,int t){\/\/线性情况：连续长度未len，最大数为t, 
	if(len==1)return ll(t+1);
	if(len==2)return ((t+1)*(t+1) );
	for(int i=0;i<=len;i++)f[i][0]=f[i][1]=0;
	f[0][0]=t,f[0][1]=1;
	f[1][0]=(t+1)*t;
	f[1][1]=t+1;
	for(int i=2;i<len;i++){
		f[i][1]=(f[i-1][0]+f[i-1][1])%mod;
		f[i][0]=(f[i-1][1]*t+f[i-2][1]*t*t)%mod;
	} 
	return (f[len-1][0]+f[len-1][1])%mod;
}
 
int main(){

	cin>>n;
	for(int i=0;i<n;i++)cin>>b[i],b[i+n]=b[i]; 
	for(int i=0;i<n;i++){
		a[i]=min(min(b[(i-1+n)%n],b[i]),b[(i+1)%n]);
		a[i+n]=a[i];
	}
	memset(c,-1,sizeof(c));
	int flag=-1;
	for(int i=0;i<n;i++) { \/\/先把可以确定的确定。 
		if(b[(i-1+n)%n]<b[i])c[(i+1)%n]=c[(i+1)%n+n]=b[i],flag=(i+1)%n;
		else if((b[(i-1+n)%n]>b[i]))c[(i-2+n)%n]=c[(i-2+n)%n+n]=b[(i-1+n)%n],flag=(i-2+n)%n;
	}

	\/\/找出连续的数据段。
	if(flag==-1){\/\/所有数据一样，构成环。 
		ans=work(n,a[0]);
		if(n==4)ans=(ans-(ll)pow(a[11],3))%mod;
		else if(n>4)ans= (ans-(ll)pow(a[11],4)-2*(ll)pow(a[11],3))%mod;
		if(ans<0)ans+=mod;
		cout<<ans<<endl;
		return 0;
	}
	int len=0;
	for(int i=flag;i<=n+flag;i++) {
		if(c[i%n]>-1)len=0;
		else {
			len++;
			if(c[(i+1)%n]>-1){
				ll tmp=work2(len,a[i%n]);
				ans=ans*tmp%mod;
			}
		}
		
	}
	cout<<ans<<endl;
	
} 

\/*
6
8 8 8 5 5 4
366
*\/