题解 CF152E 【Garden】
VenusM1nT
2020-11-02 21:04:28
好久没做 $\textbf{DP}$ 题了。
观察到 $k\leq 7$，于是可以考虑状压。以 $0/1$ 代表是否造了当前这座大厦。
可是题目给定的是一个网格图，只考虑是否造的话肯定不对，因此引入 $i,j$ 来代表这个位置是否被覆盖过了。
然后考虑转移。每次枚举 $S,i,j$ 和 $s\in S$，考虑容斥，则得到：
$$f_{S,i,j}=f_{s,i,j}+f_{S-s,i,j}-a_{i,j}$$
这一步是对上一状态的转移，接下来考虑当前状态的计算，要求的是最少毁多少花，其实就是一个最短路，因此每个点从它周围四个点转移过来就可以了，当然这里要多做几次，保证取到最优解（题解里另外一位神仙是 $n\times m+10$ 次，我稍微多循环了几次，也没什么问题）。复杂度 $\text{O}(2^k\times n^2\times m^2)$，因为 $n\times m\leq 200$ 所以没有压力。
上述的是最优解的求法，但答案还要求输出方案。不过这题的方案不难输，可以记录每个点每个状态的前驱，最后递归一下就可以求出来了。
```cpp
#include<bits/stdc++.h>
#define N 100
#define St 200
#define reg register
#define inl inline
using namespace std;
int n,m,K,f[N+5][N+5][St],pre[N+5][N+5][St][3],a[N+5][N+5];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
bool res[N+5][N+5];
void Print(reg int x,reg int y,reg int S)
{
res[x][y]=1;
if(pre[x][y][S][0]==2) return;
if(!pre[x][y][S][0]) Print(pre[x][y][S][1],pre[x][y][S][2],S);
else
{
Print(x,y,pre[x][y][S][1]);
Print(x,y,pre[x][y][S][2]);
}
}
int main()
{
scanf("%d %d %d",&n,&m,&K);
for(reg int i=1;i<=n;i++)
{
for(reg int j=1;j<=m;j++) scanf("%d",&a[i][j]);
}
for(reg int S=0;S<(1<<K);S++)
{
for(reg int i=1;i<=n;i++)
{
for(reg int j=1;j<=m;j++) f[i][j][S]=1e9;
}
}
for(reg int i=1;i<=K;i++)
{
reg int x,y;
scanf("%d %d",&x,&y);
f[x][y][1<<(i-1)]=a[x][y];
pre[x][y][1<<(i-1)][0]=2;
}
for(reg int S=0;S<(1<<K);S++)
{
for(reg int i=1;i<=n;i++)
{
for(reg int j=1;j<=m;j++)
{
for(reg int k=S;k;k=(k-1)&S)
{
reg int cnt=f[i][j][k]+f[i][j][S^k]-a[i][j];
if(cnt<f[i][j][S])
{
f[i][j][S]=cnt;
pre[i][j][S][0]=1;
pre[i][j][S][1]=k;
pre[i][j][S][2]=S^k;
}
}
}
}
for(reg int o=1;o<=n*m+N;o++)
{
for(reg int i=1;i<=n;i++)
{
for(reg int j=1;j<=m;j++)
{
for(reg int k=0;k<4;k++)
{
reg int nx=i+dx[k],ny=j+dy[k];
if(nx<1 || nx>n || ny<1 || ny>m) continue;
reg int cnt=f[nx][ny][S]+a[i][j];
if(cnt<f[i][j][S])
{
f[i][j][S]=cnt;
pre[i][j][S][0]=0;
pre[i][j][S][1]=nx;
pre[i][j][S][2]=ny;
}
}
}
}
}
}
reg int ans=1e9;
for(reg int i=1;i<=n;i++)
{
for(reg int j=1;j<=m;j++) ans=min(ans,f[i][j][(1<<K)-1]);
}
printf("%d\n",ans);
for(reg int i=1;i<=n;i++)
{
for(reg int j=1;j<=m;j++)
{
if(f[i][j][(1<<K)-1]==ans)
{
Print(i,j,(1<<K)-1);
for(reg int k=1;k<=n;k++)
{
for(reg int l=1;l<=m;l++) printf("%c",res[k][l]?'X':'.');
puts("");
}
return 0;
}
}
}
}
```