这题对于每个帽子有三种情况： 1. 没有被打开 2. 打开后没有硬币 3. 打开后有硬币 于是我们可以用 3n 的时间枚举出所有情况 而后 n2 的判断这种情况是否可行，然后取价值最大的那种即可 代码如下：
#include<bits/stdc++.h> using namespace std; #define M 15 #define N 2000005 int n,m,k,num,Hcnt; int dp[N],cntx[M],cnty[M],tmp[M],val[M],Hx[M],Hy[M]; char str[M]; struct node{ int x,y; }Q[M]; void Min(int &a,int b){ if(a==-1||a>b)a=b; } void Max(int &a,int b){ if(a<b)a=b; } void solve(int x){ memset(Hx,0,sizeof(Hx)); memset(Hy,0,sizeof(Hy)); int Coin=k,Hat=Hcnt,Cnt=num; for(int i=0;i<Hcnt;i++){ if(x/tmp[i]%3){ Hat--; Cnt--; } if(x/tmp[i]%3==2){ Coin--; Hx[Q[i].x]++; Hy[Q[i].y]++; } } if(Hat<Coin)return; if(!Coin){ for(int i=0;i<n;i++) if((Hx[i]+cntx[i])%2)return; for(int i=0;i<m;i++) if((Hy[i]+cnty[i])%2)return; dp[x]=0; return; } int res=-1; for(int i=0;i<Hcnt;i++){ if(x/tmp[i]%3)continue; int mi=-1; if(Hat>Coin&&~dp[x+tmp[i]])Min(mi,dp[x+tmp[i]]); if(~dp[x+2*tmp[i]])Min(mi,dp[x+2*tmp[i]]+(Cnt>0)); if(~mi)Max(res,mi); } if(~res)dp[x]=res; } int main(){ scanf("%d %d %d %d",&n,&m,&k,&num); for(int i=0;i<n;i++){ scanf("%s",str); for(int j=0;j<m;j++) if(str[j]=='H'){ Q[Hcnt++]=(node){i,j}; cntx[i]++;cnty[j]++; } } for(int i=1;i<=k;i++)scanf("%d",&val[i]); tmp[0]=1; for(int i=1;i<=Hcnt;i++)tmp[i]=tmp[i-1]*3; memset(dp,-1,sizeof(dp)); for(int i=tmp[Hcnt]-1;i>=0;i--)solve(i); if(dp[0]==-1)puts("-1"); else { int res=0; sort(val+1,val+k+1); for(int i=1;i<=dp[0];i++)res+=val[i]; printf("%d\n",res); } return 0; }