14015problem I 方案数

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