1. 首页
  2. 题解列表
  3. 1531题题解

蓝桥杯算法提高VIP-数的划分 （C++代码）

378 阅读 0 评论
原题链接：蓝桥杯算法提高VIP-数的划分

解题思路:

dp/mdfs

注意事项:

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <iostream>
#include <vector>
#define N 110
 
using namespace std;
 
vector< vector<int> > ans;
long long cache[N][N];
long long dp[N][N];
 
long long solve_dfs_dbg(int preNum, int res, vector<int> arr)
{
    if (res == 0)
    {
        ans.push_back(arr);
        return 1LL;
    } 
    else if (res < 0) return 0LL;
    else
    {
        long long sum = 0;
        for (int i = preNum; i <= res; i++)
        {
            arr.push_back(i);
            sum += solve_dfs_dbg(i, res - i, arr);
            arr.pop_back();
        }
             
        return sum;
    }
}
 
long long solve_dfs(int preNum, int res)
{
    if (cache[preNum][res] != 0)
        return cache[preNum][res];
    if (res == 0) return 1LL;
    else if (res < 0) return 0LL;
    else
    {
        long long sum = 0;
        for (int i = preNum; i <= res; i++)
            sum += solve_dfs(i, res - i);
        cache[preNum][res] = sum;
        return sum;
    }
}
 
long long solve_dp(int n)
{
    for (int i = 0; i <= n; i++)
        dp[i][0] = 1;
    for (int i = n; i >= 0; i--)
        for (int j = 1; j <= n; j++)
            for (int k = i; k <= j; k++)
                    dp[i][j] += dp[k][j - k];
    return dp[1][n];
}
 
int main()
{
    int n = 0;
    cin >> n;
    //cout << solve_dfs(1, n) << endl;
    cout << solve_dp(n) << endl;
    return 0;
}


点赞(0)
　

0 分

0 人评分

　

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

一笔画问题（dfs）
一笔画问题（dfs）
C++ ： 类和两种访问权限的练习
C++ ： 类和两种访问权限的练习
C++ ： 类和两种访问权限的练习
C++ ： 类和两种访问权限的练习
幸运儿（约瑟夫环-模拟+ Vector）
幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

暂无评论