AcWing 5357. π日
原题链接
中等
作者:
ywt51
,
2024-10-20 20:00:49
,
所有人可见
,
阅读 2
#include <bits/stdc++.h>
using namespace std;
int n, k, f[255][255][255];
//f[i][j][k] 只使用前i个数,总和j个,选了k个的方案数
int main()
{
cin >> n >> k;
f[0][0][0] = 1; //用0,总和是0,选了0个数的方案数 是合法方案 方案数是1
for (int i = 1; i <= n; ++ i) //阶段
for (int j = 0; j <= n; ++ j) //状态1 总和是j
for (int s = 0; s <= k; ++ s) //状态2 选了s个数
{
f[i][j][s] = f[i-1][j][s]; //没有使用第i个数
if (j >= i) f[i][j][s] += f[i][j-i][s-1]; //使用了第i个数,完全背包的模型
}
cout << f[n][n][k];
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n, k, f[255][255];
//f[n][k][n]
int main()
{
cin >> n >> k;
f[0][0] = 1; //空间省略一个维度,删除阶段
for (int i = 1; i <= n; ++ i)
for (int j = i; j <= n; ++ j)
for (int s = 1; s <= k; ++ s)
f[j][s] += f[j-i][s-1];
cout << f[n][k];
return 0;
}