题意:
给你n个数字,挑出任意多个,要求最小和最大的差值不小于x且总和在l和r之间,问有多少种方案
思路:
由于n极小,那么我们可以直接状态压缩,用二进制表示每个数字的使用状态,然后看是否符合要求即可
错误及反思:
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 20;
long long arr[maxn];
int n;
long long l,r,x;
int main()
{scanf("%d%lld%lld%lld",&n,&l,&r,&x);for(int i=0;i<n;i++)scanf("%lld",&arr[i]);long long xx=1;for(int i=0;i<n;i++)xx*=1ll*2;int ans=0;for(long long i=0;i<xx;i++){long long temp=i;vector<long long> v;long long all=0;int now=0;while(temp){if(temp%2){v.push_back(arr[now]);all+=arr[now];}now++;temp/=2;}if(all>=l&&all<=r){sort(v.begin(),v.end());if(v[v.size()-1]-v[0]>=x)ans++;}}printf("%d\n",ans);
}