题目描述
给定 n 个字符串 s1,s2,…,sn。
每个字符串 si 的长度均在 [1,6] 范围内且均由小写字母 a∼j(即前 10 个小写字母)构成。
现在,我们要在字母 a∼j 和数字 0∼9 之间确立一种字母与数字的一一对应关系,每个字母对应一个数字,不同字母对应的数字不同。
确立的对应关系需满足:
将给定的 n 个字符串中的每个字母替换为对应数字后,可以得到 n 个不含前导 0 的正整数。得到的 n 个正整数之和应尽可能小。请你计算并输出得到的 n 个正整数之和的最小可能值。
输入保证至少存在一种满足条件的对应关系。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个字符串 si。
输出格式
一个整数,表示得到的 n 个正整数之和的最小可能值。
数据范围
前 3 个测试点满足 1≤n≤5。
所有测试点满足 1≤n≤1000。
算法1
(暴力枚举)
思路
1. 枚举每一个字母对应的数字,计算最小值
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
public class Main {
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
solve01();
pw.flush();
}
static long s1ans=Long.MAX_VALUE;
private static void solve01() throws IOException {
String[] s=br.readLine().split(" ");
int[] alp=new int[10];
int n=Integer.parseInt(s[0]);
Set<Integer> cs=new HashSet<Integer>();
for(int i=0;i<n;i++) {
char[] st=br.readLine().toCharArray();
int m=st.length;
cs.add(st[0]-'a');
for(int j=m-1,l=0;j>=0;j--,l++) {
alp[st[j]-'a']+=Math.pow(10, l);
}
}
boolean[] vis=new boolean[10];
for(int i=0;i<10;i++) {
if(i==0) {
if(cs.contains(0)) {
continue;
}
}
vis[i]=true;
s1dfs(1, i, alp, cs, alp[0]*i,vis);
vis[i]=false;
}
pw.println(s1ans);
}
private static void s1dfs(int curalp, int curselect, int[] alp, Set<Integer> cs, long tans,boolean[] vis) {
if(curalp==10) {
s1ans=Math.min(s1ans, tans);
return;
}
for(int i=0;i<10;i++) {
if(i==0) {
if(cs.contains(curalp)) {
continue;
}
}
if(vis[i]) {
continue;
}
vis[i]=true;
s1dfs(curalp+1, i, alp, cs, tans+alp[curalp]*i,vis);
vis[i]=false;
}
}
}