SRM549 Div1 600

/* 对于每一个帽子有3个状态(1 没有开 2 开了有硬币 3 开了没有硬币) 由于题目有限制条件，如果我们每次转移的时候都判断一下太麻烦了 又因为帽子的摆放和硬币在掀开所有的帽子后的是确定的所以可以再最后判断 */ #include<bits/stdc++.h> using namespace std; const int M=15,INF=1555,N=1694323; int dp[N],val[M]; int hat,n,m,B[M],k,guess_num; char str[M][M]; bool X[M],Y[M]; struct pos{int x,y;}A[M]; int dfs(int S,int c,int num){ if(~dp[S])return dp[S]; int &ans=dp[S];ans=0; if(!c){//所有的硬币都放好了 memset(X,0,sizeof(X)); memset(Y,0,sizeof(Y)); for(int i=0;i<hat;i++){ int nw=S/B[i]%3; int x=A[i].x,y=A[i].y; if(nw!=2)X[x]^=1,Y[y]^=1;//偶数不影响答案 } for(int i=0;i<n;i++)if(X[i])return ans=INF; for(int i=0;i<m;i++)if(Y[i])return ans=INF; return ans; } if(!num){//取完了 for(int i=0;i<hat;i++){ if(!(S/B[i]%3)&&!dfs(S+B[i]*2,c-1,0)) return ans=0; //看看剩下的硬币放这里行不行 }return ans=INF;//不可以 } for(int i=0;i<hat;i++){ int nw=S/B[i]%3; if(!nw){ int get_it=dfs(S+B[i]*2,c-1,num-1)+1; int not_get_it=dfs(S+B[i],c,num-1); ans=max(ans,min(get_it,not_get_it)); } }return ans; } int main(){ memset(dp,-1,sizeof(dp)); scanf("%d %d %d %d",&n,&m,&k,&guess_num); for(int i=0;i<n;i++)scanf("%s",str[i]); for(int i=0;i<n;i++)for(int j=0;j<m;j++) if(str[i][j]=='H')A[hat++]=(pos){i,j}; for(int i=0;i<k;i++)scanf("%d",val+i); B[0]=1;for(int i=1;i<M;i++)B[i]=B[i-1]*3; sort(val,val+k); int mx=dfs(0,k,guess_num); if(hat<k||mx==INF){puts("-1");return 0;} int ans=0; for(int i=0;i<mx;i++)ans+=val[i];//因为B足够聪明我们给A最小的即可 printf("%d",ans); }