CodeForces 550B Preparing Olympiad(DFS回溯+暴力枚举)

红太狼 2021-05-02 15:04 556阅读 0赞

【题目大意】

一组题目的数目（n<=15），每一个题目有对应的难度，问你选择一定的题目（大于r个且小于l个）且选择后的题目里最小难度与最大难度差不小于x，求选择方案数。

【解题思路】：

DFS+回溯。

先发一发比較拙的代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e5+10;
  4. int num[N],mum[N];
  5. int n,m,q,t,l,r;
  6. int top,ans,cnt;
  7. void dfs(int sum,int d,int x,int minn)///和。极值,当前循环。最小数
  8. {
  9.     if(sum>=l&&sum<=r&&d>=q) ans++;
  10.     if(sum>r) return;
  11.     ///if(sum<l) return;当前累加的sum可能小于l
  12.     for(int i=x;i<=n;++i)
  13.     {
  14.         dfs(sum+num[i],num[i]-minn,i+1,minn);
  15.     }
  16. }
  17. int main()
  18. {
  19.     while(cin>>n>>l>>r>>q)
  20.     {
  21.         ans=0;
  22.         memset(num,0,sizeof(num));
  23.         for(int i=1; i<=n; ++i) scanf("%d",&num[i]);
  24.         sort(num+1,num+1+n);
  25.         for(int i=1; i<=n; ++i)
  26.         {
  27.             dfs(num[i],0,i+1,num[i]);///为了參照最大和最小,引入最小数
  28.         }
  29.         printf("%d\n",ans);
  30.     }
  31.     return 0;
  32. }

发表评论

表情：
评论列表 （有 0 条评论，556人围观）

还没有评论，来说两句吧...

相关阅读

    相关 ACM.暴力枚举

    \有一类问题可以采用一种盲目的搜索方法，在搜索结果的过程中，把各种可能的情况都考虑到，并对所得的结果逐一进行判断，过滤掉那些不符合要求的，保留那些符合要求的，这种方法叫枚举算法

    我就是我我就是我/ 0 赞/ 82 阅读

    相关 507 完美数（暴力枚举）

    1. 问题描述： 对于一个正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为 「完美数」。给定一个整数 n， 如果是完美数，返回 true，否则返回 false

    - 日理万妓- 日理万妓/ 0 赞/ 325 阅读

    相关 暴力枚举

    Problem Description 小埋今天出门准备买一堆漫画书回来，书的套餐类型有 3 种，第一种书是单本的，第二种书是两本捆在一起的，第三种是三本书捆在一起的。每

    矫情吗；*矫情吗；*/ 0 赞/ 326 阅读