LOJ

分析

考虑二分图。对于每一行、列被 # 隔开的每一段拿出来当做一个点，然后对于每个点从其所属的行连通块向列连通块连边。

但是每个连通块内可以放多个棋子。假设一个连通块内放了 $x$ 个棋子，那么会产生 $\frac{x(x-1)}{2}$ 的费用，我们要最小化费用。

考虑费用递增。由于 $\frac{(x+1)x}{2}-\frac{x(x-1)}{2}=x$，所以我们只需要连若干条容量为 $1$、费用为 $x$ 的边即可。

这样子每次增广的流量为 $1$，所以可以费用流算出流量为 $i$ 时的最小费用（即放 $i$ 个棋子时的答案），询问直接查一下即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50+10;
const int V=2500+10,E=5000000+10;

int n,tot,ans[N*N]; char s[N][N];
int idx[N][N],idy[N][N],sz[N*N];

struct edge { int v,w,c,nxt; } e[E<<1];
int head[V];
void addEdge(int u,int v,int w,int c) {
    static int cnt=1;
    e[++cnt]=(edge){v,w,c,head[u]},head[u]=cnt;
    e[++cnt]=(edge){u,0,-c,head[v]},head[v]=cnt;
}

int S,T,dis[V],inq[V],lst[V];
int spfa() {
    memset(dis,0x3f,sizeof(dis)),memset(lst,0,sizeof(lst));
    queue<int> Q; Q.push(S); dis[S]=0;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(),inq[u]=0;
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (e[i].w&&dis[u]+e[i].c<dis[v]) {
                dis[v]=dis[u]+e[i].c,lst[v]=i;
                if (!inq[v]) Q.push(v),inq[v]=1;
            }
        }
    }
    return lst[T]!=0;
}

void mcmf(int lim) {
    int maxflow=0,mincost=0;
    while (spfa()&&maxflow<lim) {
        for (int i=lst[T];i;i=lst[e[i^1].v]) --e[i].w,++e[i^1].w;
        ++maxflow,mincost+=dis[T];
        ans[maxflow]=mincost;
    }
}

int main() {
    n=read(); int c=0;
    for (int i=1;i<=n;++i) {
        scanf("%s",s[i]+1);
        for (int j=1;j<=n;++j) if (s[i][j]=='.') ++c;
    }
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j) {
            if (s[i][j]=='#') continue;
            if (s[i][j]!=s[i][j-1]) idx[i][j]=++tot;
            else idx[i][j]=idx[i][j-1];
        }
    int totx=tot;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j) {
            if (s[j][i]=='#') continue;
            if (s[j][i]!=s[j-1][i]) idy[j][i]=++tot;
            else idy[j][i]=idy[j-1][i];
        }
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            if (s[i][j]!='#') ++sz[idx[i][j]],++sz[idy[i][j]];
    S=0,T=tot+1;
    for (int i=1;i<=totx;++i)
        for (int j=0;j<sz[i];++j) addEdge(S,i,1,j);
    for (int i=totx+1;i<=tot;++i)
        for (int j=0;j<sz[i];++j) addEdge(i,T,1,j);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            if (s[i][j]=='.') addEdge(idx[i][j],idy[i][j],1,0);
    mcmf(c);
    int Q=read();
    for (int i=1;i<=Q;++i) printf("%d\n",ans[read()]);
    return 0;
}