cf#302 E. Remembering Strings 状压dp

点击打开链接

题意：给定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;}