两种记忆化的写法都过不了

写法1 最简单的思路，对区间排序后，深搜每个区间选与不选的最大值即可，不过需要记忆化当前选到第几个区间与当前右端点。

测试点3 不开O2 TLE，开了O2MLE。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1.5e5 + 10;
int n; PII A[N]; map<PII, int> f;

int dfs(int u, int r)
{
    if (u > n) return 0;
    if (f.count({u, r})) return f[{u, r}];
    int& v = f[{u, r}];
    
    v = max(v, dfs(u + 1, r));
    if (A[u].first > r)
        v = max(v, dfs(u + 1, A[u].second)
                    + A[u].second - A[u].first + 1);
    
    return v;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> A[i].first >> A[i].second;
    
    sort(A + 1, A + 1 + n);
    
    cout << dfs(1, 0);
    
    return 0;
}

写法2 参考了题解之后，深搜每一个点，如果这个点能扩展到右区间就去遍历其最大值，以及不扩展。只需要记忆化当前点的最大值即可。

测试点3 MLE (可能因为搜索深度爆炸？ 3e6的深度?

#include <bits/stdc++.h>
using namespace std;

const int N = 3e6 + 10;
int n, m, f[N]; vector<int> g[N];

int dfs(int u)
{
	if (u > m) return 0;
	int& v = f[u]; if (v != -1) return v;

	for (auto& i : g[u])
		v = max(v, dfs(i + 1) + i - u + 1);
	v = max(v, dfs(u + 1));

	return v;
}

int main()
{
	cin >> n;
	for (int i = 1, a, b; i <= n; i++)
	{
		cin >> a >> b; g[a].push_back(b);
		m = max(m, b);
	}

	memset(f, -1, sizeof f);
	cout << dfs(0);

	return 0;
}

所以这道题用记忆化搜索不能AC嘛？（倔强