题意
给定一些等长的仅有小写字母组成的字符串，要求把每一个字符串变为好记的，定义为存在它的某一位字符在所有字符串中那一位独特，给定变换某个字符串某一位的代价，不限制把它转换成什么小写字母，问达到要求的最少的代价是多少
思路
状态压缩dp，用二进制表示字符串是否好记，1表示好记，0表示不好记，dp值表示到当前状态的最少代价，每一次转移只需考虑最低的为0的一位，两种可能，一种是把它变出去，另一种是在跟它相同（包括自己）的里边仅保留最大的，把其它的都换走，这样可以转移到下一个状态了，对每一个状态不断地更新到最小值，最后全1的状态的值就是答案
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 1000000001
char s[
21][
21];
int a[
21][
21];
int dp[
1<<
20];
int main()
{
int n,m,e,add,maxx,change;
cin>>n>>m;
for(
int i=
0;i<n;i++)
cin>>s[i];
for(
int i=
0;i<n;i++)
for(
int j=
0;j<m;j++)
cin>>a[i][j];
e=(
1<<n);
for(
int i=
1;i<e;i++)
dp[i]=INF;
for(
int i=
0;i<e;i++)
for(
int j=
0;j<n;j++)
if(!((i>>j)&
1))
{
for(
int k=
0;k<m;k++)
{
dp[i|(
1<<j)]=min(dp[i|(
1<<j)],dp[i]+a[j][k]);
add=
0;
maxx=
0;
change=
0;
for(
int l=
0;l<n;l++)
{
if(s[j][k]==s[l][k])
{
add+=a[l][k];
maxx=max(maxx,a[l][k]);
change|=(
1<<l);
}
}
dp[i|change]=min(dp[i|change],dp[i]+add-maxx);
}
break;
}
printf(
"%d\n",dp[e-
1]);
return 0;
}
