警钟酸蚀

P1464 Function

junhaowang @ 2024-07-18 11:25:21

关于为什么 RE（指记忆化）

本蒟蒻太过于蒟蒻，居然连着四个提交记录都 RE 了！

下面是一些注意事项，可能有些问题，请批评指正。如果有其他的事项欢迎补充。

  1. 负数下标访问数组会 RE。
  2. 数组开太小会 RE（建议大于 20 的不要存数组）
  3. 直接开数组还有很多迷之错误，蒟蒻懒得调了。

干脆负数也处理了吧。怎么办呢？

开个 map 呗！

这里我们可以建立一个 map<tuple<int,int,int>,int> mp 表示把一个 tuple 映射到 int 上，不再有这么严苛的大小限制。

然后就没有然后了。访问怎么办？看下面。

原来：f[a][b][c] \longrightarrow 现在：f[make_tuple(a,b,c)]

经验证可以 AC。

by junhaowang @ 2024-07-18 11:27:09

附 AC 提交记录：https://www.luogu.com.cn/record/166831052

代码：

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
using namespace std;

#define int long long
#define rint register int
#define endl '\n'
#define debug(x) cerr << #x << '=' << x << endl;

int a, b, c;
map <tuple <int, int, int>, int> f;

int dfs(int a, int b, int c)
{
    if (f[make_tuple(a, b, c)])
    {
        return f[make_tuple(a, b, c)];
    }
    if (a <= 0 || b <= 0 || c <= 0)
    {
        return f[make_tuple(a, b, c)] = 1;
    }
    if (a > 20 || b > 20 || c > 20)
    {
        return dfs(20, 20, 20);
    }
    if (a < b && b < c)
    {
        return f[make_tuple(a, b, c)] = dfs(a, b, c - 1)
                                        + dfs(a, b - 1, c - 1)
                                        - dfs(a, b - 1, c);
    }
    return f[make_tuple(a, b, c)] = dfs(a - 1, b, c)
                                    + dfs(a - 1, b - 1, c)
                                    + dfs(a - 1, b, c - 1)
                                    - dfs(a - 1, b - 1, c - 1);
}

signed main(void)
{
    while (true)
    {
        //难得地用起了scanf
        scanf("%lld %lld %lld", &a, &b, &c);
        if (!~a && !~b && !~c)
        {
            break;
        }
        printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, dfs(a, b, c));
    }
    return 0;
}
|