大佬教程收集整理的这篇文章主要介绍了CF543C Remembering Strings 状压dp,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
Code:
#include <cstdio> #include <algorithm> #include <cString> #define setIO(s) freopen(s".in","r",stdin) #define inf (1<<22) #define maxn 30 using namespace std; char s[maxn][maxn]; int data[maxn][maxn],common[maxn][maxn],b[maxn][maxn],dp[inf],n,m; int main() { // setIO("input"); scanf("%d%d",&n,&m); for(int i=0;i<n;++i) scanf("%s",s[i]); for(int i=0;i<n;++i) for(int j=0;j<m;++j) scanf("%d",&data[i][j]); for(int i=0;i<n;++i) for(int j=0;j<m;++j) { int sum=0,x=-inf; for(int k=0;k<n;++k) { if(s[k][j]==s[i][j]) { sum+=data[k][j],x=max(x,data[k][j]); common[i][j]|=(1<<k); } } b[i][j]=sum-x; } memset(dp,0x3f,sizeof(dp)),dp[0]=0; int re=(1<<n); for(int i=0;i<re;++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]+data[j][k]); dp[i|common[j][k]]=min(dp[i|common[j][k]],dp[i]+b[j][k]); } } printf("%d\n",dp[re-1]); return 0; }
以上是大佬教程为你收集整理的CF543C Remembering Strings 状压dp全部内容,希望文章能够帮你解决CF543C Remembering Strings 状压dp所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。