数的划分
题目 数的划分
思路分析
从n中选k个数 组合型枚举 但是这里不一样的是 他两个位置上的数可以重复 仅是顺序不能颠倒上做了限制
所以这里枚举的时候 下一位无需从i+1处枚举 直接从i开始即可
仅加位数不够的剪枝只能过3/5
发现题目还有个sum的要求 那么就可以把它也做参数传入 进行一个剪枝
居然还被卡了 过4/5
看了题解发现 tm这是dp的题
噶写多了dfs 看不出来dp了
震惊的是dfs居然能基本过 （dp白学了 bushi）
但是这个dp不太好懂 就这样写吧
也有一个很牛的dfs剪枝ac了
虽然dfs没有dp快，但是这道题数据很小如果在比赛中dp和dfs同样能过那最好还是用dfs，因为dfs的思路简单不容易错而且代码好写方便改错。这里因为要考虑到不重复，所以可以按升序记录每一次划分：记录上一次划分所用的数，保证当前划分所用数不小于上次划分所用分数，当划分次数等于k时比较该次划分所得总分是否与n相同并记录次数。
有一个不得不做的剪枝就是枚举当前划分所用分数时应该从last(上次划分所用分数)枚举到sum+i*(k-cur)<=n为止，因为之后划分的分数一定大于或等于当前划分所用分数。这个剪枝不做的话不仅会TLE，在TLE之前就爆栈RE了
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int n,k,cnt;
void dfs(int last,int sum,int cur){
if(cur==k){
if(sum==n)
cnt++;
return;
}
//for(int i=last;sum+i*(k-cur)<=n;i++)
for(int i=last;sum+i<=n;i++)
dfs(i,sum+i,cur+1);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
dfs(1,0,0);
cout<<cnt<<endl;
return 0;
}
//其实就是说 sum剪枝的地方放在dfs之前 而不是dfs之后
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=210,M=10;
int a[N];
int path[M];
int res;
int n,k;
void dfs(int u,int start,int sum){
if(sum>n) return;
if(u+n-start<k) return;
if(u>k){
if(sum==n){
res++;
}
return;
}
for(int i=start;i+sum<=n;i++){
path[u]=i;
dfs(u+1,i,sum+i);
path[u]=0;
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
a[i]=i;
dfs(1,1,0);
cout<<res<<endl;
return 0;
}
代码实现
3/5
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=210,M=10;
int a[N];
int path[M];
int res;
int n,k;
void dfs(int u,int start){
if(u+n-start<k) return;
if(u>k){
int sum=0;
for(int i=1;i<=k;i++)
sum+=path[i];
if(sum==n){
// for(int i=1;i<=k;i++)cout<<path[i]<<" ";cout<<endl;
res++;
}
return;
}
for(int i=start;i<=n;i++){
path[u]=i;
dfs(u+1,i);//可以重复选 但有顺序 所以从i开始即可
path[u]=0;
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
a[i]=i;
dfs(1,1);
cout<<res<<endl;
return 0;
}
4/5
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=210,M=10;
int a[N];
int path[M];
int res;
int n,k;
void dfs(int u,int start,int sum){
if(sum>n) return;
if(u+n-start<k) return;
if(u>k){
if(sum==n){
// for(int i=1;i<=k;i++)cout<<path[i]<<" ";cout<<endl;
res++;
}
return;
}
for(int i=start;i<=n;i++){
path[u]=i;
dfs(u+1,i,sum+i);
path[u]=0;
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
a[i]=i;
dfs(1,1,0);
cout<<res<<endl;
return 0;
}
同类题型
视频讲解
⬅️ 迷宫 🏠 00-刷题理模型 ➡️ 组合型（n中选m 不考虑顺序）
💬 评论