求大佬加个记忆化
查看原帖
求大佬加个记忆化
1446545
XHZnewlife楼主2024/12/25 13:10
#include<bits/stdc++.h>
using namespace std;
long long ans=1;long long m[200005],a[200005];long long n;
int dfs(bool t,long long o,long long z){
	if(t==0){
		o=min(a[z]-1,o);
		if(z!=n){
			ans+=dfs(0,o,z+1);
		    ans+=dfs(1,o,z+1);
		}
	}
	if(t==1){
		o=min(m[z]-a[z],o);
		if(z!=n){
			ans+=dfs(0,o,z+1);
		    ans+=dfs(1,o,z+1);
		}
	}
	if(z==n)return o;
	return 0;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m[i];
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dfs(0,INT_MAX,1);
	dfs(1,INT_MAX,1);
	cout<<ans%1000000007;
	return 0;
}

t了好多……

2024/12/25 13:10
加载中...