华师一附中OI组

标题: 炸弹坑问题 [打印本页]
作者: admin    时间: 2018-6-2 18:59
标题: 炸弹坑问题
一排有n个坑，每个坑都可以放炸弹，但是不可以连续m个坑放炸弹，输入n和m，请问有多少种放炸弹的方法。
作者: admin    时间: 2018-6-2 19:01
显然可以用dfs来做，枚举每个坑是放炸弹还是不放，用s表示当前这一列的连续炸弹数目，要是这个坑不放炸弹，就归0了，这样除了复杂度高点之外，显然是可以出结果的。
作者: 张笑宇    时间: 2018-7-27 20:07
  1. #include<iostream>
  2. using namespace std;
  3. int n,m,ans=0,a[10010];
  4. void dfs(int x)
  5. {
  6.     if (x>=n+1)
  7.     {
  8.         int s=0;
  9.         for (int i=1;i<=n;i++)
  10.         {
  11.             if (a[i]==1) s++;
  12.             else s=0;
  13.             if (s>=m) return;
  14.         }
  15.         ans++;
  16.         return;
  17.     }
  18.     a[x]=1;
  19.     dfs(x+1);
  20.     a[x]=0;
  21.     dfs(x+1);
  22. }
  23. int main()
  24. {
  25.     cin>>n>>m;
  26.     dfs(1);
  27.     cout<<ans;
  28.     return 0;
  29. }
复制代码
作者: 张笑宇    时间: 2018-7-27 20:07
全排列 再判断
作者: 黄煦喆    时间: 2018-7-27 20:29
  1. #include<iostream>
  2. using namespace std;
  3. int n,m,ans,a[101],cnt;
  4. void ms(int i,int x)
  5. {
  6.     if(i>n)ans++;
  7.     else
  8.     {
  9.         if(x+1<m)
  10.         {
  11.             a[i]=1;
  12.             ms(i+1,x+1);
  13.             a[i]=0;
  14.         }
  15.         ms(i+1,0);
  16.     }
  17. }
  18. int main()
  19. {
  20.     cin>>n>>m;
  21.     ms(1,0);
  22.     cout<<ans;
  23.     return 0;
  24. }
复制代码
作者: admin    时间: 2018-7-27 23:12
这个题可以用递推来做的 。
作者: zhwang    时间: 2018-7-30 00:32
  1. #include<cstdio>
  2. int n,m;
  3. int sum=0;
  4. int book[10001];
  5. void dfs(int step,int x)
  6. {
  7.         if(step==m)
  8.         {
  9.                 return;
  10.         }
  11.         else
  12.         {
  13.                 if(x==n+1)
  14.                 {
  15.                         sum++;
  16.                         return;
  17.                 }
  18.         }
  19.         dfs(0,x+1);
  20.         dfs(step+1,x+1);
  21. }
  22. int main()
  23. {
  24.         scanf("%d%d",&n,&m);
  25.         book[1]=1;
  26.         dfs(0,1);
  27.         printf("%d",sum);
  28.         return 0;
  29. }
复制代码
作者: zhwang    时间: 2018-7-30 00:35
话说我总觉得这题有什么数学公式，但是想不出来，动态规划的话应该就是和‘拖拉机’纸牌游戏一样讨论放与不放写两个类似于数学推倒的关系式，但是写完暴搜好晚了。总感觉上面递推大佬的式子有点奇怪，不知道是自己太蒟蒻了还是真的有问题。
作者: zhwang    时间: 2018-7-30 00:39
zhwang 发表于 2018-7-30 00:32

喵？book数组好像没有用到啊……好尴尬啊



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2