福建省法冶建设知识有奖网站,网站建设分为几个阶段,网站域名需要申请,湖南网站建设联系电话dfs剪枝
思路#xff1a;暴力枚举搜索#xff0c;不过要优雅剪枝一下下
1:处理重复情况--我们只需要然后方取值从前往后的时候呈现递增#xff08;可以相等#xff0c;即不递减#xff09;
2#xff1a;剪枝--基于上思想#xff0c;剩下的“盘子”里面的数至…dfs剪枝
思路暴力枚举搜索不过要优雅剪枝一下下
1:处理重复情况--我们只需要然后方取值从前往后的时候呈现递增可以相等即不递减
2剪枝--基于上思想剩下的“盘子”里面的数至少都大于等于当前“盘子”的数所以我们取完当前盘子的数完就可判断--剩下的盘子取最小即取都当前盘子的数看总和还不会超过n会那肯定不满足sumi*(k-pos1)n
3ACcode:
#includebits/stdc.h
using namespace std;
#define int long long
int n,k,cnt;
void dfs(int pos,int now,int sum) {if(posk1){if(sumn) cnt;//刚好 return;}//剪枝sumi*(k-pos1)n for(int inow;sumi*(k-pos1)n;i){dfs(pos1,i,sumi);}
}
void solve() {cinnk;dfs(1,1,0);coutcnt\n;
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);solve();return 0;
}
dp
思路
f[i][x] 表示 i 分成 x 个非空的数的方案数。
显然 ix 时 f[i][x]0 , ix 时 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:
#includebits/stdc.h
using namespace std;
#define int long long
int n,k,f[2005][10];
void solve() {cinnk;for(int i1;in;i){f[i][1]1;f[i][0]1;}for(int i2;ik;i){f[1][i]0;}for(int i2;in;i)for(int j2;jk;j){if(ij)f[i][j]f[i-1][j-1]f[i-j][j];else f[i][j]f[i-1][j-1];}coutf[n][k];
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);solve();return 0;
}
over~
