题目描述
某地发行一套彩票。彩票上写有1到M这M个自然数。彩民可以在这M个数中任意选取N个不同的数打圈。每个彩民只能买一张彩票，不同的彩民的彩票上的选择不同。
每次抽奖将抽出两个自然数X和Y。如果某人拿到的彩票上，所选N个自然数的倒数和，恰好等于X/Y，则他将获得一个纪念品。
已知抽奖结果X和Y。现在的问题是，必须准备多少纪念品，才能保证支付所有获奖者的奖品。
输入输出格式
输入格式：
输入文件有且仅有一行，就是用空格分开的四个整数N，M，X，Y。
输出格式：
输出文件有且仅有一行，即所需准备的纪念品数量。
1≤X, Y≤100，1≤N≤10，1≤M≤50。
输入数据保证输出结果不超过10^5。
输入输出样例
输入样例#1：
2 4 3 4
输出样例#1：
1
搜索+疯剪(疯狂剪枝)
还要注意精度
剪枝：可行性剪枝
如果之后的几个最大倒数的和相加小于x/y
或最小倒数的和相加大于x/y就可以剪枝
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int ans,n,m;
double p,s[];
void dfs(int cen,int x,double sum)
{
if (sum+s[x+n-cen]-s[x]-p<=-1e-) return;
if (sum+s[m]-s[m-n+cen]-p>=1e-) return;
if (cen>=n&&fabs(sum-p)<=1e-)
{
ans++;
return;
}
if (sum-p>=1e-) return;
if (cen>=n) return;
dfs(cen,x+,sum);
dfs(cen+,x+,sum+(double)(1.0/(double)(x+)));
}
int main()
{int i;
double x,y;
cin>>n>>m>>x>>y;
p=x/y;
for (i=;i<=m;i++)
s[i]=s[i-]+(1.0/(double)i);
s[m+]=s[m];
dfs(,,);
cout<<ans;
}