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
解題思路
- 首先利用搜索與回溯的方法求出所有組合數，
- 減去重復的個數，
附上代碼
#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://www.uj5u.com/qita/227868.html
標籤：其他