信息
- ID
- 659
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 26
- 已通过
- 13
- 上传者
从小到大地划分
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define MOD 998244353
using namespace std;
int n,k,ans;
//x记录上一个选的数,并且要求这次选的数要不小于上次选的数
void dfs(int x,int now,int sum)
{
// cout<<x<<" "<<now<<" "<<sum<<endl;
if(now==k)
{
if(sum<=n-x)
{
ans++;
// cout<<ans<<endl;
}
return;
}
for(int i=x;sum+i<=n;i++)
dfs(i,now+1,sum+i);
// book[x][k-now]=0;
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
dfs(1,1,0);
cout<<ans<<endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n, k;
int ans;
// 考虑第 now 份怎么分
// 最少分 minN 个,之前所有数之和为 sum
void dfs(int now, int minN, int sum)
{
if (now > k)
{
if (sum == n)
ans++;
return;
}
//之前的和为 sum
//now 后面的 (k-now) 个数都至少是 minN
for (int i = minN; i <= n - sum - (k - now) * minN; i++)
dfs(now + 1, i, sum + i);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
ans = 0;
dfs(1, 1, 0);
cout << ans << "\n";
return 0;
}
dp[i][j]
: i
分成 j
组非 0
的方案数dp[i-1][j-1]
: i
分成 j
份,至少存在一组大小为 1
的方案数dp[i-j][j]
: i
分成 j
份,不存在大小为 1
的组方案数(先每个位置都铺一个 1
,然后再要求分成 j
份,不允许为空)#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
int dp[205][10];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++)
dp[i][1] = 1;
for (int i = 1; i <= n; i++)
for (int j = 2; j <= k; j++)
if (i >= j)
dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];
cout << dp[n][k] << endl;
return 0;
}