张世民

用户名：zsm123

访问量：655

签　名：

等　　级
排　　名	41342
经　　验	317
参赛次数	2
文章发表	2
年　　龄	0
在职情况	学生
学　　校	怀化学院
专　　业

　　自我简介：

TA的其他文章

题目 1531: 蓝桥杯算法提高VIP-数的划分
浏览：149

你可能喜欢

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

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

题目 1531: 蓝桥杯算法提高VIP-数的划分

　　作者: 张世民　　　　发表时间：2020-05-06 15:10:34 浏览：149　|　评论：0　

法一：动态规划DP, 按位计算，最后累加。
我们用dp[i][j]来表示把i划分为j份的方法，直接想方程不好想，我假设已经划分好了i
i = a1 + a2 + … + aj
不妨把每一个a都减去1
i-j = (a1-1) + (a2-1) + a(aj-1)
这时分法与原来一样
dp[i][j] = dp[i - j][1] + dp[i - j][2] +…+ dp[i - j][j - 1] + dp[i - j][j]
dp[i - 1][j - 1] = dp[i - j][1] + dp[i - j][2]… + dp[i - j][j - 1]
由上面两式推出：
dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j]
代码1

import java.util.Scanner;
	public class Main {
	public static int[][] dp = new int[105][105];
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		int n =sc.nextInt();
		dp[0][0] = 1;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n && j <= i; j++) {
				dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
			}
		}
		int sum = 0;
		for(int i = 1; i<=n; i++) {
			sum += dp[n][i];
		}
		System.out.println(sum);
		}
	}
代码二：

#include<iostream>
	#include<algorithm>
	using namespace std;
	const int N = 110;
	int dp[N][N];
	int main(void)
	{
	    int n;
	    scanf("%d",&n);
	    for(int i=1;i<=n;i++) dp[i][0]=0;
	    for(int i=0;i<=n;i++) dp[0][i]=1;
	    //dp[i][j]表示把i拆分成不超过j的方案数 
	    for(int i=1;i<=n;i++)
		{
	        for(int j=1;j<=n;j++)
	        {
	            //dp[i][j]只有包含j和不包含j两种情况
	            //dp[i][j-1]不包含j,dp[i-j][j]包含若干个j 
	            if(i>=j) dp[i][j]=dp[i][j-1]+dp[i-j][j]; 
	            else dp[i][j]=dp[i][i]; 
	        } 
	    }
	    printf("%d",dp[n][n]);
	    return 0;
	}

法二：记忆化搜索
vis[m][k]为把m分成k份的种类数，将每种情况都存储下来，下次dfs到他的时候就可以直接取用而不是继续去重复的浪费时间去递归。
m < k 时，即盒子多，球少，没法构造成k位数，则直接返回0;
盒子为1时，无论球多少，只有一种情况，即{m};
盒子与球相等时，则只有一种情况，每个盒子只能放一个球，即{1,1,1,1,1…}!
否则就是球数大于盒子数分为两种情况：
有1的序列，即至少有一个1，即dfs(m - 1, k - 1)，从m中拿一个球放到k中，再将m - 1个球放到剩下的k - 1个盒子里；
没有1的序列，即每个盒子里至少大于等于2个球，即dfs(m - k, k), 先从m 个球中取 k 个球放到 k 个盒子里，再将剩下的m - k 个球放到 k 个盒子里， 这样就能保证每个盒子至少两个球，若m - k 后的值 小于k 则相当于 dfs(m, k) = dfs(m - 1, k - 1) + dfs(m - j ,k),即最后变为 dfs(m, k) = dfs(m - 1, k - 1) + 0；
所以最终递推公式：dfs(m, k) = dfs(m - 1, k - 1) + dfs(m - j ,k)

#include <string>
	#include <cstdio>
	#include <iostream>
	#include <algorithm>
	using namespace std;

int n, sum, k;
	int vis[1010][1010];

//将m个求放到k个盒子
	int dfs(int m, int k)
	{
	    if(vis[m][k]) return vis[m][k];
	    //球数小于盒子数无法填满盒子，返回0
	    if(m < k) return 0;
	    //盒子数为1和盒子数为球数只有一种情况
	    if(k == 1 || k == m) return 1;
	    //球数大于盒子数则递归
	    return vis[m][k] = dfs(m - k, k) + dfs(m - 1, k - 1);
	}

int main()
	{
		cin >> n;
		for(int i = 1; i <= n; i++) sum += dfs(n, i);
		cout << sum << endl;
		return 0;
	}

0.0分

0 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

张世民

TA的其他文章

你可能喜欢

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

C二级辅导-温度转换（C++代码）

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

C语言训练-字符串正反连接（C语言代码）

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

题目 1531: 蓝桥杯算法提高VIP-数的划分

评论区

精彩推荐

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

淘淘的名单（C语言代码）

【偶数求和】（C语言代码）

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

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

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

程序员的表白（C语言代码）

简单的a+b （C语言代码）

C语言训练-8除不尽的数（C语言代码）

JAM计数法（C语言代码）

张世民

TA的其他文章

你可能喜欢

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

C二级辅导-温度转换 （C++代码）

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

C语言训练-字符串正反连接 （C语言代码）

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

题目 1531: 蓝桥杯算法提高VIP-数的划分

评论区

精彩推荐

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

淘淘的名单 （C语言代码）

【偶数求和】 （C语言代码）

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

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

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

程序员的表白 （C语言代码）

简单的a+b （C语言代码）

C语言训练-8除不尽的数 （C语言代码）

JAM计数法 （C语言代码）

C二级辅导-温度转换（C++代码）

C语言训练-字符串正反连接（C语言代码）

　　评论区

淘淘的名单（C语言代码）

【偶数求和】（C语言代码）

程序员的表白（C语言代码）

C语言训练-8除不尽的数（C语言代码）

JAM计数法（C语言代码）