原题P1310 [NOIP2011 普及组] 表达式的值

[10个点5个MLE] (https://www.luogu.com.cn/record/82659668)

内存爆了，不知道是dfs原因，还是map 我更倾向于是map

#include<bits/stdc++.h>
using namespace std;
map<int,map<int,int> >t1,t2;
string s;
int n;
int find(char ch,int l,int r)
{
	if(ch!=')')
	{
	for(int i=l;i<=r;i++)
		if(ch==s[i])
			return i;
	return -1;
	}
	else
	{
		for(int i=r;i>=l;i--)
		if(ch==s[i])
			return i;
		return -1;
	}
}
long long dfs1(int l,int r);
long long dfs2(int l,int r);
int main()
{
	cin>>n;
	cin>>s;
	int ans=dfs1(0,n-1);
	printf("%d",ans%10007);
	return 0;
}
long long dfs1(int l,int r)//变成0 
{
	if(t1[l][r]!=0) return t1[l][r];
	if(t1.size()>=9999)
		t1.clear();
	if(l>r)//一个空区间，1，0都可变 
		return 1;
	if(l==r)
	{
		if(s[l]=='*') return 3;
		if(s[l]=='+') return 1;
		return 1;
	 } 
	 if(s[l]=='('&&s[r]==')') 
		return dfs1(l+1,r-1);
	/*if(find('(',l,r)!=-1)
	{
		int x1=find('(',l,r),x2=find(')',l,r);
		if(x1==l&&x2==r)
			t1[l][r]=dfs1(l+1,r-1);
		else
		{
			if(x1!=l)
		}
	}
	else*/ 
	{
		if(find('+',l,r)!=-1)
		{
			int x=find('+',l,r);
			t1[l][r]=dfs1(l,x-1)*dfs1(x+1,r);
		}
		else
		{
			int x=find('*',l,r);
			t1[l][r]+=dfs1(l,x-1)*dfs1(x+1,r);
			t1[l][r]+=dfs1(l,x-1)*dfs2(x+1,r);
			t1[l][r]+=dfs2(l,x-1)*dfs1(x+1,r);
		}
	}
	t1[l][r]%=10007;
	fflush(stdin); 
	return t1[l][r];
}
long long dfs2(int l,int r)//变成1 
{
	if(t2[l][r]!=0) return t2[l][r];
	if(t2.size()>=9999)
		t2.clear();
	if(l>r)//一个空，1，0都可变 
		return 1;
	if(l==r)
	{
		if(s[l]=='*') return 1;
		if(s[l]=='+') return 3;
	 } 
	if(s[l]=='('&&s[r]==')') 
		return dfs2(l+1,r-1);
	{
		if(find('+',l,r)!=-1)
		{
			int x=find('+',l,r);
			t2[l][r]+=dfs1(l,x-1)*dfs2(x+1,r);
			t2[l][r]+=dfs2(l,x-1)*dfs1(x+1,r);
			t2[l][r]+=dfs2(l,x-1)*dfs2(x+1,r);
		}
			
		else
		{
			int x=find('*',l,r);
			t2[l][r]=dfs2(l,x-1)*dfs2(x+1,r);
			
		}
	}
	t2[l][r]%=10007;
	/*int t=t2[l][r];
	t2.clear();
	t2[l][r]=t;*/
	return t2[l][r];
}

代码很长，但是比较好理解（bushi）

只需要各位dalao 告诉我怎么优化内存就行

如果需要代码解释的@我就好，我去吃饭 逃

呼叫大佬：

@ken887

@haimo

@wangjunjie2020

@ccyx505