不记忆化我超时，记忆化了以后WA了看不出记忆化哪里错了求调

问题讨论区 普及段
21

好的，但我不是巨佬，我是蒟蒻

22

o所以我哪里错了？

23

没人了只能@巨佬了 @金杭东 @桑铃茜 @黎俊博1 @王建力

24

这题和这算法有啥关系

25

@金杭东 啥意思？

26

感觉不是记忆化做的

27

@金杭东 好像是的？题解里面是st表+线段树，但是我的记忆化哪里错了呢？我搞不懂

28

70了

ll dfs(ll x, ll step) {
    if (mem[x].count(step)) return mem[x][step];  // 如果已经计算过，直接返回

    if (step == 10) return ans;  // 达到递归深度限制，返回结果

    ll i = n / x + 1;  // 计算下一个值

    ll current_ans = ans;

    // 计算最大值
    if (i >= L && i <= R) current_ans = max(current_ans, n % i);
    if (i != 0) current_ans = max(current_ans, dfs(n / i + 1, step + 1)); 
    if (i > 1) current_ans = max(current_ans, dfs(n / (i - 1) + 1, step + 1));  

    // 存储结果
    mem[x][step] = current_ans;
    return current_ans;
}
29

@王建力 这是改了哪里老师？

30

@王建力 但是老师应该判断 mem.count(x) 吧，step只是记录dfs深度的

31

这是最新代码 WA70：

#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi  0
#define int long long
I AK IOI;
int n,m,ans,L,R;
unordered_map<int,unordered_map<int,int> >mem;
int dfs(int x,int step){
    if(mem[x].count(step))return mem[x][step];
    if(step==10) return ans;
    int i=n/x+1;
    int cur=ans;
    if(i>=L&&i<=R)cur=max(cur,n%i);
    if(i!=0)cur=max(cur,dfs(n/i+1,step+1));
    if(i>1)cur=max(cur,dfs(n/(i-1)+1,step+1));
    mem[x][step]=cur;
    return cur;
}
signed main(){
    cin>>n>>m;
    int maxn=n/2+1,mmod=n%maxn;
    while(m--){
        cin>>L>>R;
        if(L<=maxn&&maxn<=R)cout<<mmod<<endl;
		else if(L>maxn)cout<<n-L<<endl;
        else{
        	mem.clear();
            ans=max(n%L,n%R);
            int l1=0,l2=0;
            int i1=n/L+1;
            if(i1>=L&&i1<=R)ans=max(ans,n%i1);
            int i2=n/R+1;
            if(i2>=L&&i2<=R)ans=max(ans,n%i2);
            int kl=n/L;
            if(kl!=0)ans=max(ans,dfs(kl,0));
			int kr=n/R;
			if(kr!=0)ans=max(ans,dfs(kr,0));
            cout<<ans<<endl;
        }
    }
    i_ak ioi;
}
32

完了，对于我这个新手，根本就找不出问题啊！！！

33

@言过 @稻叶昙 卡完常以后加了搜索深度还是WA70？

#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi  0
#define int long long
#define R register
I AK IOI;
namespace fastIO{char *p1,*p2,buf[100000];
	#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
	inline void read(int&n){int x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=nc();}while(ch>=48&&ch<=57){x=(x<<3)+(x<<1)+(ch^48),ch=nc();}n=x*f;}
	inline void read(string&s){s="";char ch=nc();while(ch==' '||ch=='\n'){ch=nc();}while(ch!=' '&&ch!='\n'){s+=ch,ch=nc();}}
	inline void read(char&ch){ch=nc();while(ch==' '||ch=='\n'){ch=nc();}}
	inline void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
	inline void write(const string&s){for(R int i=0;i<(int)s.size();i++){putchar(s[i]);}}
	inline void write(const char&c){putchar(c);}
}using namespace fastIO;
int n,m,ans,L,R1;
unordered_map<int,unordered_map<int,int> >mem;
inline int dfs(const int &x,const int &step){
    if(step==11) return ans;
    if(mem[x].count(step))return mem[x][step];
    int i=n/x+1;
    int cur=ans;
    if(i>=L&&i<=R1)cur=max(cur,n%i);
    if(i!=0)cur=max(cur,dfs(n/i+1,step+1));
    if(i>1)cur=max(cur,dfs(n/(i-1)+1,step+1));
    mem[x][step]=cur;
    return cur;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    read(n);
    read(m);
    int maxn=n/2+1,mmod=n%maxn;
    while(m--){
        read(L);
        read(R1);
        if(L<=maxn&&maxn<=R1){
        	write(mmod);
        	putchar('\n');
        }
		else if(L>maxn){
			write(n-L);
			putchar('\n');
		}
        else{
        	mem.clear();
            ans=max(n%L,n%R1);
            int l1=0,l2=0;
            int i1=n/L+1;
            if(i1>=L&&i1<=R1)ans=max(ans,n%i1);
            int i2=n/R1+1;
            if(i2>=L&&i2<=R1)ans=max(ans,n%i2);
            int kl=n/L;
            if(kl!=0)ans=max(ans,dfs(kl,0));
			int kr=n/R1;
			if(kr!=0)ans=max(ans,dfs(kr,0));
            write(ans);
            putchar('\n');
        }
    }
    i_ak ioi;
}
34

此帖子已被社区举报，现已被临时隐藏。

35

@言过 ?怎么了？这是正常卡常技巧