炸弹坑问题

admin

一排有n个坑，每个坑都可以放炸弹，但是不可以连续m个坑放炸弹，输入n和m，请问有多少种放炸弹的方法。

admin

显然可以用dfs来做，枚举每个坑是放炸弹还是不放，用s表示当前这一列的连续炸弹数目，要是这个坑不放炸弹，就归0了，这样除了复杂度高点之外，显然是可以出结果的。

张笑宇

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. }
    

复制代码

张笑宇

全排列 再判断

黄煦喆

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

这个题可以用递推来做的 。

zhwang

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

话说我总觉得这题有什么数学公式，但是想不出来，动态规划的话应该就是和‘拖拉机’纸牌游戏一样讨论放与不放写两个类似于数学推倒的关系式，但是写完暴搜好晚了。总感觉上面递推大佬的式子有点奇怪，不知道是自己太蒟蒻了还是真的有问题。

zhwang

zhwang 发表于 2018-7-30 00:32

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