北京谁会做网站开发,hao123网址导航官网,工艺品网站模版,上海做淘宝网站数的划分
ybtoj DP-1-1
题目大意
给你一个n#xff0c;让你分成k份#xff0c;问有多少种分法#xff08;1,2和2,1为同一种#xff09;
输入样例
7 3输出样例
4
样例解释
四种分法为#xff1a;1,1,5;1,2,4;1,3,3;2,2,3.1,1,5; \ \ 1,2,4; \ \ 1,3,3; \ \ 2,2,3.1…数的划分
ybtoj DP-1-1
题目大意
给你一个n让你分成k份问有多少种分法1,2和2,1为同一种
输入样例
7 3输出样例
4
样例解释
四种分法为1,1,5;1,2,4;1,3,3;2,2,3.1,1,5; \ \ 1,2,4; \ \ 1,3,3; \ \ 2,2,3.1,1,5; 1,2,4; 1,3,3; 2,2,3.
数据范围
6n⩽2002⩽k⩽66n\leqslant 2002\leqslant k\leqslant 66n⩽2002⩽k⩽6
解题思路
可以让生成序列单调递减使其不重复 如果让其单调递减那只有两种操作 1.新增1份里面有1 2.前i份全部加1 这样保证后面的加了前面的也一定会加 fi,jfi,j−ifi−1,j−1f_{i,j}f_{i,j-i}f_{i-1,j-1}fi,jfi,j−ifi−1,j−1
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
int n, k, f[10][210];
int main()
{scanf(%d%d, n, k);f[0][0] 1;for (int i 1; i k; i)for (int j i; j n; j)f[i][j] f[i][j - i] f[i - 1][j - 1];//递推printf(%d, f[k][n]);return 0;
}
