抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

洛谷P1705 爱与愁过火

题意简述

求出从 $m$ 个数中选 $r$ 个并使和大于 $r$ 的方案数。

输入:

  • $m$,$r$,$n$。
  • $m$ 个数字。
  • $m\le30$。

输出:

  • 方案数。

题目分析

因为数据范围不大,所以直接dfs即可。但是要注意优化,要不然会超时。

第一个优化,如果在搜索过程中发现剩下的不够了,那么这条搜索路线就不行了,将其剪掉。

第二个优化,如果现在的和已经比要求的大了,所以后面的不管怎么选都满足条件,使用组合公式统计答案个数即可。

组合公式:

$C^r_n=\frac{n!}{r!(n-r)!}$

第三个优化,因为选择不需要按顺序,所以排序也不影响答案的正确性,而从大到小排序更容易满足第二个优化的条件。

详情请见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;
int m, r, n; //如题所述
int num[23333]; //每个数字
int ans; //最后的答案
int tot; //所有数字的总和
bool cmp(int a, int b) //用于sort
{
return a > b;
}
double factorial(int num) //用于求阶乘,注意用double,不然数字大了会炸
{
double tmp = 1;
for (int i = 1; i <= num; ++i)
{
tmp *= i;
}
return tmp;
}
/**
* index 现在搜到的位置
* sum 到目前为止的和
* t 已经用了的数字个数
* choose 是否选择当前数字
*/
void dfs(int index, int sum, int t, bool choose)
{
if (index > m) //超出范围返回
{
return;
}
if (m - index + t + 1 < r) //如果剩下的数字个数不满r那么就直接返回
{
return;
}
if (choose) //选择了就要加上值
{
t++;
sum += num[index];
if (sum > n) //如果现在已经满足条件了,那么后面的不管怎么搜都可以了,统计方案数然后返回
{
/**
* m-index 剩余可选的个数
* r-t 要从中选择的个数
*/
ans += factorial(m - index) / factorial(r - t) / factorial(m - index - r + t);
return;
}
}
if (t == r) //如果搜完了那就返回
{
if (sum > n) //满足条件进行统计
{
ans++;
}
return;
}
dfs(index + 1, sum, t, 0); //不选下一个
dfs(index + 1, sum, t, 1); //选择下一个
}
int main()
{
cin >> m >> r >> n;
for (int i = 1; i <= m; ++i)
{
cin >> num[i];
tot += num[i];
}
if (tot <= n) //如果所有数加起来都不满n那就不可能了
{
cout << 0;
return 0;
}
if (r == m) //如果全部要选,那么就只有一种方案(总和小于n的情况已经被排除了)
{
cout << 1;
return 0;
}
sort(num + 1, num + m + 1, cmp); //这样会优先选择大数,更容易满足第40行的条件
dfs(1, 0, 0, 0); //不选第一个数
dfs(1, 0, 0, 1); //选择第一个数
cout << ans;
return 0;
}