P1025 [NOIP2001 提高组] 数的划分（dfs+剪枝 or dp）-Toy模板网

这篇具有很好参考价值的文章主要介绍了P1025 [NOIP2001 提高组] 数的划分（dfs+剪枝 or dp）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

dfs+剪枝

思路：暴力枚举搜索，不过要优雅剪枝一下下

1:处理重复情况-->我们只需要然后方取值从前往后的时候呈现递增（可以相等，即不递减）

2：剪枝-->基于上思想，剩下的“盘子”里面的数至少都大于等于当前“盘子”的数，所以我们取完当前盘子的数完，就可判断-->剩下的盘子取最小（即取都当前盘子的数，看总和还不会超过n，会那肯定不满足）（sum+i*(k-pos+1)<=n ）

3：ACcode:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,cnt;
void dfs(int pos,int now,int sum) {

   if(pos==k+1){
   	if(sum==n) cnt++;//刚好 
   	return;
   }
   //剪枝：sum+i*(k-pos+1)<=n 
   for(int i=now;sum+i*(k-pos+1)<=n;i++){
   	dfs(pos+1,i,sum+i);
   }
}
void solve() {
	cin>>n>>k;
	dfs(1,1,0);
	cout<<cnt<<"\n";
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

dp

思路：

f[i][x] 表示 i 分成 x 个非空的数的方案数。

显然 i<x 时 f[i][x]=0 , i=x 时 f[i][x]=1;

其余的状态，我们分情况讨论：

①有1的 ②没有1的

第一种情况，方案数为 f[i-1][x-1]

第二种情况，方案数为 f[i-x][x] (此时 i 必须大于 x)

所以，状态转移方程为： f[i][x]=f[i-1][x-1]+f[i-x][x]

ACcode:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,f[2005][10]; 
void solve() {
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		f[i][1]=1;
		f[i][0]=1;
	}
	for(int i=2;i<=k;i++){
		f[1][i]=0;
	}
	for(int i=2;i<=n;i++)
	for(int j=2;j<=k;j++){
		if(i>j)f[i][j]=f[i-1][j-1]+f[i-j][j];
		else f[i][j]=f[i-1][j-1];
	}
	cout<<f[n][k];
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

over~文章来源地址https://www.toymoban.com/news/detail-619281.html

到了这里，关于P1025 [NOIP2001 提高组] 数的划分（dfs+剪枝 or dp）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！