點擊打開鏈接

題意：給定n個長度均為m的字符串，下面n行給出字符串，下面n*m的矩陣表示把對應的字母修改成其他字母的花費。

   對于一個字符串，若它是easy to remembering 當 它存在一個字母，使得這個字母在這一列是獨一無二的。

  要使得n個字符串都是easy to remembering 的最小花費。

  第一個樣例是把第一列的4個a中3個a修改成別的字母，所以花費為3.

思路：

因為最多只有20個字符串，也就是修改后的字母種類至多只有20種。

然后狀壓已經easy to remembering的字符串的最小花費。

dp[i] 表示已經easy to remembering 的字符串狀態為i時的最小花費。

兩個轉移：

1、直接修改字母

2、把這一列中所有與這個字母相同的字母都修改成別的字母。

當然可以剩下一個，剩下花費最大的那個即可。

cost[i][j] 就表示除了花費最大的那個 同列中與str[i][j]字母相同的花費和。

bit[i][j] 表示哪些字符串 在第j列 與 a[i][j] 字母相同。

代碼：

#include <bits/stdc++.h>using namespace std;char s[30][30];int a[30][30];int bit[30][30],cost[30][30],dp[(1<<21)+1];int main(){	int n,m; 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];	for(int i=0; i<n; i++)		for(int j=0; j<m; j++){			int ans=0, mx=-1;			for(int k=0; k<n; k++){				if(s[i][j] == s[k][j]){					ans += a[k][j];					mx = max(mx,a[k][j]);					bit[i][j] |= (1<<k);				}			}			cost[i][j] = ans - mx;		}	memset(dp,0x3f,sizeof(dp)); 	dp[0] = 0;	for(int i=0; i<(1<<n); i++){		for(int j=0; j<n; j++){			if((i&(1<<j)) == 0){				for(int k=0; k<m; k++){					dp[i|(1<<j)] = min(dp[i|(1<<j)],dp[i]+a[j][k]);					dp[i|bit[j][k]] = min(dp[i|bit[j][k]],dp[i]+cost[j][k]); 				}			}		}	}	cout << dp[(1<<n)-1] << endl;}