欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

14015problem I 方案数

程序员文章站 2022-03-15 11:39:06
14015problem I 方案数计时器游戏结束后,晨晨的同学明明取了其中的K个计时器设计出拼数字游戏:明明和晨晨各自把K个计时器排成一行,看谁拼出的数最大。例如:有K=3个计时器,上面数字分别是31,3,331,两人拼的方案分别是:明明拼的数字是333131,晨晨拼的数字是331313,显然明明赢。明明掌握了拼出最大值的核心算法,晨晨下决心也要研究。不过她首先要编程统计这K个计时器能拼出多少种不同的方案?注意,现在的计时器更先进,可以显示4位数字。输入第一行:1个整数K。(1 ≤ K...

14015problem I 方案数

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

明明拼的数字是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

相关标签: UPC专栏 dfs