P7171 [COCI2020-2021#3] Selotejp

· · 题解

P7171 题解

2021.10.29 修改了一些语言表述问题。

题意：

有 n\times m 个格子，一些是"#"，一些是"."，每次可以将连续个"#"涂色，不可重复涂色，求最少涂抹次数。

分析：

一道经典的 dp 问题，考虑普通状压转移过于复杂，还会超时，所以使用轮廓线 dp。

我们设 dp_{i,j,k} 为在扫描前 i 行第 j 个元素时，前 m 个数的二进制状态（0 为横着涂，1 为竖着涂，不可涂色部分默认为 0）为 k 时的答案贡献。

（此时二进制状态从低位到高位应分别对应前 m 的数、前 m-1 的数等等，以此类推）

（对于“前 i 的数”的顺序的定义，可以理解为矩阵一般的搜索顺序）

解决：

确定状态后，我们考虑该如何转移。

对于当前所找的元素，如果为"#"，则 dp_{i,j+1,k>>1}（即下个元素横着涂）可由 dp_{i,j,k}（若未超界且当前元素为横）或 dp_{i,j,k}+1（若未超界且当前元素为竖）转移过去；

以此类推，dp_{i,j+1,(k>>1)+(1<<m-1)}（即下个元素竖着涂）也可以这样转移。

如果当前元素为"."，则直接转移贡献即可。

（可能有点难读懂，那就展现读者强大的阅读能力吧！）

代码：

#include<bits/stdc++.h>
using namespace std;
int dp[1005][15][2050];
int n,m,M;
char c[1005][15];
int ans;
int maxn=1000000007;
int main()
{
    cin>>n>>m;M=1<<m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>c[i][j];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<M;k++)
                dp[i][j][k]=maxn;

    if(c[1][1]=='#') dp[1][1][0]=dp[1][1][1<<m-1]=1;
    else dp[1][1][0]=0;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<M;k++)
            {
                if(dp[i][j][k]>=maxn) continue;
                int nj=j%m+1,ni=i;
                if(j==m) ni=i+1;
                if(c[ni][nj]=='#')
                {
                    if(nj>1&&!(k&1<<m-1)&&c[i][j]=='#') dp[ni][nj][k>>1]=min(dp[ni][nj][k>>1],dp[i][j][k]);
                    else dp[ni][nj][k>>1]=min(dp[ni][nj][k>>1],dp[i][j][k]+1);
                    if(ni>1&&(k&1)&&c[ni-1][nj]=='#') dp[ni][nj][(k>>1)+(1<<m-1)]=min(dp[ni][nj][(k>>1)+(1<<m-1)],dp[i][j][k]);
                    else dp[ni][nj][(k>>1)+(1<<m-1)]=min(dp[ni][nj][(k>>1)+(1<<m-1)],dp[i][j][k]+1);
                }
                else dp[ni][nj][k>>1]=min(dp[ni][nj][k>>1],dp[i][j][k]);
            }

    ans=maxn;
    for(int i=0;i<M;i++)
        ans=min(ans,dp[n][m][i]);

    cout<<ans;
    return 0;
}

朴素~~奇丑~~的代码。

谢谢观看！！