网站建设哪些公司好,如何创建微网站,一般公路建设招投标在什么网站上,线下推广有哪几种渠道题干#xff1a;
题目描述
将整数n分成k份#xff0c;且每份不能为空#xff0c;任意两个方案不相同(不考虑顺序)。
例如#xff1a;n7#xff0c;k3#xff0c;下面三种分法被认为是相同的。
1,1,5 1,5,1 5,1,1
问有多少种不同的分法。
输入输出格式
输入格式
题目描述
将整数n分成k份且每份不能为空任意两个方案不相同(不考虑顺序)。
例如n7k3下面三种分法被认为是相同的。
1,1,5 1,5,1 5,1,1
问有多少种不同的分法。
输入输出格式
输入格式 n,kn,k (6n \le 2006n≤2002 \le k \le 62≤k≤6) 输出格式 11个整数即不同的分法。 输入输出样例
输入样例#1 复制
7 3输出样例#1 复制
4说明
四种分法为 1,1,51,1,5; 1,2,41,2,4; 1,3,31,3,3; 2,2,32,2,3.
解题报告 这题也是今年十月份左右的时候清理工邀请赛的第二签到题。。当时想不到办法了直接dfs过的。偶然翻洛谷看到了原题、、见到了dp解法和母函数的解法。 dfs很简单做个简单的剪枝就好了这是个看似o(200^6)但是实际上远远没有这么高复杂度的dfs。今天先补上dp的解法母函数的以后复习的时候再说。
AC代码1dfs
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
ll dp[505][505];
int n,k;
void dfs(int last,int sum,int cur) {if(curk) {if(sumn) cnt;return;}for(int ilast; sumi*(k-cur)n; i) {//剪枝只用枚举到sumi*(k-cur)n为止dfs(i,sumi,cur1);}
}
int main()
{cinnk;dfs(1,0,0);cout cnt endl;return 0 ;}AC代码2dp
dp[i][j]代表把i个小球放到j个盒子中的方法数。
一个简单的想法:以一个数为基准逐步减少分割数 或 减少待分割数 。这里选择1
分为两种情况因为是无序的所以认为每次都是划分完后所有球从小到大排序了
a.至少有一个盒子只有一个小球的情况数
b.没有一个盒子只有一个小球的情况数
这样进行划分是因为这种分类可以使a和b都有能写出来的表达式
a.因为盒子不加区分那么1的情况数与“将n-1个小球放到k-1个盒子中”的情况数一样
b.没有一个盒子只有一个小球那么把每个盒子中拿出来一个小球对应的是“把(n-k)个小球放到k个盒子中的情况数”
这个b情况可以理解为第一个数不为1时可以视为先在所有的位置上都加上一个1再对于所有的位置用新的总数求次数
所以定了的是占有了总数j个位置仍然是j个与原来相比没有变化。所以b情况的方案数把i-j个球放到j个盒子中的方案数。
然后将上面的思路化为动态转移方程
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
ll dp[505][505];
int main()
{int n,k;for(int i 1; i303; i) /*dp[i][0] */dp[i][1] 1;//那一句到底有没有必要加啊反正是这个状态用不到dp[1][1] 1;for(int i 2; i303; i) {for(int j 2; ji; j) {if(i-j 0) dp[i][j] dp[i-1][j-1] dp[i-j][j];//其实要是ji这么写的话这一行前面的那个if也可以不要了//else dp[i][j] 0;}}cinnk;cout dp[n][k]endl;return 0 ;}总结 注意一下dp这里的数组不能开dp[505][25]这样如果要这么写的话那就加上else也是错的因为你想啊i会遍历到300那j也会跟着到300所以会越界啊就修改别的数据了所以保险起见要么你在内层循环写上jmin(k,i)或者min(15,i)要么就直接开个打数组来存这些没用的状态就好了嘛反正也是用不到的状态恰好也不会卡住空间干脆就开这么大好了。
题解https://www.luogu.org/problemnew/solution/P1025
