14015problem I 方案数

计时器游戏结束后,晨晨的同学明明取了其中的K个计时器设计出拼数字游戏:明明和晨晨各自把K个计时器排成一行,看谁拼出的数最大。例如:有K=3个计时器,上面数字分别是31,3,331,两人拼的方案分别是:

明明拼的数字是333131,晨晨拼的数字是331313,显然明明赢。
明明掌握了拼出最大值的核心算法,晨晨下决心也要研究。不过她首先要编程统计这K个计时器能拼出多少种不同的方案?
注意,现在的计时器更先进,可以显示4位数字。

输入
第一行:1个整数K。(1 ≤ K ≤ 4)
第二行K个整数:表示K个计时器上的数。(所有数均为大于0小于10000的整数)

输出
一个整数,表示拼成不同数的方案数。
样例输入 Copy
3
31 3 331
样例输出 Copy
5
解题思路

  1. 首先利用搜索与回溯的方法求出所有组合数。
  2. 减去重复的个数。
    附上代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int n,a[100],b[100],c[100],v[100],k,len,t,x,i,ans;   //a数组放n个输入的值,b数组为搜索条件,0可搜,1不可搜
                                                         //c数组是暂存a中的值, v数组用于记录去重的下标 
long long d[100];
char s[100][100];
long long fun (long long x){   //判断位数 
	int t=0;
	do{ 
		t++;
		x=x/10;
	}while(x);
	return t;
}
void dfs(int x){     
	   for(int i=1;i<=n;i++){             //搜索种类个数 
	   	 if(x==n+1) {  t=0;              //如果搜索的个数满足要求,将该次搜索的值放到d数组中 
	   	 	         for(int i=1;i<=n;i++)
	   	 	          {  
	   	 	            t+=fun(c[i]);         //计算的时候先确定每个数的位数 
	   	 	            d[k]=d[k]+pow(10,len-t)*c[i];  
					  } 
					k++;    //记录有多少种组合 
	   	 	           return;
			        }
		 else { 
		 	      if(b[i]==0){   //如果当前i没用 才可搜索 
		 	      	  c[x]=a[i]; //暂存到c数组中方便计算每次的组合 
		 	      	  b[i]=1;
		 	      	  dfs(x+1); //搜索 
		 	      	  b[i]=0; //回溯 
				   }      		 	     					
		      }
	   }
}
int main(){ 
    memset(b,0,sizeof(int));
    scanf("%d",&n);
    for(i=1;i<=n;i++)
     { scanf("%d",&a[i]); //输入值 
      len+=fun(a[i]);   //计算n个数的总位数 
     }
    dfs(1);  //搜索 
	 ans=k;   
  for(int i=0;i<k;i++){ 
  	  for(int j=0;j<k;j++)
  	   if(d[i]==d[j]&&i!=j&&v[j]==0&&v[i]==0){ 
  	   	                                      ans--;
  	   	                                      v[j]=1;
		                                     }//每次找到一个相同的总组合数减1,并且v[j]=1 
		                            
  }
  printf("%lld",ans);
  return 0;
}

如果实在不理解搜索,可以尝试一下全排列,这题搜索思路与那题一致。

本文地址:https://blog.csdn.net/qq_52273733/article/details/110137218