题意
给定一些等长的仅有小写字母组成的字符串,要求把每一个字符串变为好记的,定义为存在它的某一位字符在所有字符串中那一位独特,给定变换某个字符串某一位的代价,不限制把它转换成什么小写字母,问达到要求的最少的代价是多少
思路
状态压缩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;
}