Catshao

用户名：Catshao

访问量：25581

签　名：

stO KHIN Orz

等　　级
排　　名	172
经　　验	6749
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

【小灰】树状数组动画详解
浏览：160

vector、deque、list的速度和内存的比较
浏览：471

Dotcpp编程2021年七月月赛题面
浏览：709

你可能喜欢

记忆化搜索解法-题解（C++）

　　作者: Catshao　　　　发表时间：2021-02-22 11:16:42 浏览：249　|　评论：1　

原题链接：A+B+C+D

# Part 1 爆搜

万物皆可暴力，这道题我们不妨先打一个暴力。
这里我使用了爆搜：

```cpp
#include <cstdio>
using namespace std;

const int MAX_N = 1010; // 最大值

long long search(int sum, int digit)
{
    // sum: 可分配的数字总和
    // digit: 分配几个数字
    if (digit > sum) { // 正整数，分配不出来0和负数
        return 0;
    }
    if (digit == 1) { // 叶子节点不能分了，返回1
        return 1;
    }
    long long cnt = 0;
    for (int i = 1; i <= sum - digit + 1; ++i) { // sum - digit + 1为当前值可选择的极限，上下界剪枝
        cnt += search(sum - i, digit - 1);
    }
    return cnt;
}

int main()
{
    int t, e;
    scanf("%d", &t);
    for (int i = 0; i < t; ++i) {
        scanf("%d", &e);
        printf("%d\n", search(e, 4));
    }
}
```

仔细读题后，我们发现ABCD都必须是**正整数**，那么当`位数 > 需要分的值`时，就如5个人分4个瓜，是分不到没人一个的，没有合适解，**返回0（无解）**

当位数只有一个时（我们默认它合法，即为正整数），只能分一次，故**返回1**

当位数为`i != 1`的时候，我们要枚举`第i位`的数字。正整数，那么下限为1，步长也为1，但是上限呢？
比如说有5个人，7个瓜，第一个人要给其余四个分瓜，每人最少拿一个，那么第一个人可以在1 ~ 3之间取瓜的个数。由此，上限就为`sum - (digit - 1)`，展开后为**`sum - digit + 1`**，保证了数据和合法性。
接下来，我们只需要将所有`i - 1`的情况累加，然后**返回累加的和**就可以了。

这个暴力只能拿27分，因为其中有大量底层的**重复计算**。

# Part 2 记忆化

既然有大量重复计算，我们可以将其保存在一个数组`mark`中。如果对于当前的`sum`和`digit`已经有人算过了，那么无需再算，直接从mark中拿走数据即可。
如果mark中没有当前数据，我们只需要用**暴力的逻辑**算一遍，然后更新到mark中即可。

经过计算，本题digit分布为`1 ~ 4`，sum分布为`0 ~ 1000`，不会MLE。

记忆化搜索需要一个标识来表示当前没有被搜索过，这里可以另开一个数据记录，或者**赋值为-1**。本文采用了后者。

## 代码

```cpp
#include <cstdio>
using namespace std;

const int MAX_N = 1010; // 最大值

long long mark[5][MAX_N]; // 记忆化

long long search(int sum, int digit)
{
    // sum: 可分配的数字总和
    // digit: 分配几个数字
    if (digit > sum) { // 正整数，分配不出来0和负数
        return 0;
    }
    if (digit == 1) { // 叶子节点不能分了，返回1
        return 1;
    }
    if (mark[digit][sum] != -1) { // 看看有没有计算过，拿来用
        return mark[digit][sum];
    }
    long long cnt = 0;
    for (int i = 1; i <= sum - digit + 1; ++i) { // sum - digit + 1为当前值可选择的极限，上下界剪枝
        cnt += search(sum - i, digit - 1);
    }
    mark[digit][sum] = cnt; // 利人利己
    return cnt;
}

int main()
{
    int t, e;
    scanf("%d", &t);

for (int i = 1; i <= 4; ++i) { // 记忆化初始化
        for (int j = 0; j < MAX_N; ++j) {
            mark[i][j] = -1;
        }
    }

for (int i = 0; i < t; ++i) {
        scanf("%d", &e);
        printf("%d\n", search(e, 4));
    }
}
```

--------------

本题数据量并不大，因此记忆化不会被卡，请求加强数据。

0.0分

1 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

Catshao

这其实是一道排列组合题目，被我愣生生打成了暴力（雾（（

2021-02-22 11:17:54

Catshao

TA的其他文章

你可能喜欢

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

川哥的吩咐（C++代码）

九宫重排（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

记忆化搜索解法-题解（C++）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

回文数(一) （C语言代码）

IP判断（C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

WU-程序员的表白（C++代码）

Catshao

TA的其他文章

你可能喜欢

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

川哥的吩咐 （C++代码）

九宫重排 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

记忆化搜索解法-题解（C++）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

回文数(一) （C语言代码）

IP判断 （C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

WU-程序员的表白 （C++代码）

C二级辅导-进制转换（C语言代码）

川哥的吩咐（C++代码）

九宫重排（C++代码）

　　评论区

IP判断（C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

WU-程序员的表白（C++代码）