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;   
}

  

上一篇:文件描述符


下一篇:python 监听键盘输入