Codeforces 543C Remembering Strings 题解

xiaoxiao2021-02-27  162

题意

给定一些等长的仅有小写字母组成的字符串,要求把每一个字符串变为好记的,定义为存在它的某一位字符在所有字符串中那一位独特,给定变换某个字符串某一位的代价,不限制把它转换成什么小写字母,问达到要求的最少的代价是多少

思路

状态压缩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; }
转载请注明原文地址: https://www.6miu.com/read-15118.html

最新回复(0)