首页 > 代码库 > Laoj P1272 取数

Laoj P1272 取数

2024-11-19 17:54:02   203人阅读

问题背景
动态规划入门-第21题
试题描述
从1，2，。。。，n中任取k个数，要求所取的k个数中，任意两个数不能相差1。编程求有多少种取法。
如：n=6 ，k=3,，从1，2，3，4，5，6中取3个数，任意两个数不能相差1，取法如下：
（1  3  5） （1  3   6） （1  4  6） （2  4  6）
共有4种取法。
提示：（1  3  5）和（3  1  5）属于一种取法。
输入格式
一行，n和k，中间用空格隔开
(1<=k<=n<=100)
输出格式
一行，取法的种数。
输入示例
6 3
输出示例
4

 

【分析】

因为任意两数不能相邻，所以dp[i][j]=dp[i-1][1]+...+dp[i-1][j-2]。

注意这里要用long long，否则可能会爆。

还有当n<2k-1时，不存在这样的取数方案。

 

【代码】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 long long n, k, ans, dp[105][105];
 5 
 6 int main() {
 7     cin >> n >> k;
 8     if (k==1)
 9         cout << n << endl;
10     for (int i=2;i<=k;++i)
11         for (int j=i*2-1;j<=n;++j)
12             if (i==2)
13                 dp[i][j]=j-2;
14             else
15                 for (int t=1;t<=j-2;++t)
16                     dp[i][j]+=dp[i-1][t];
17     for (int i=1;i<=n;++i)
18         ans+=dp[k][i];
19     cout << ans << endl;
20 }

 

Laoj P1272 取数


联系
我们