题解 P4294 【[WC2008]游览计划】

· · 题解

题意

一张 n\times m 的网格，网格有权值，某些格子必须取，问能覆盖所有必须取的点的连通块的最小权值。

题解

最近在做轮廓线dp于是就用轮廓线水了一发。

其实如果稍微理解一下的话就是[JLOI2009]神秘的生物的改编了。 (看这年份可能是JLOI改编这道题)

首先是对于必须选的点，我们赋极小值，使其必须选中，再把这部分权值加回来。以后的讨论就不用管必选与否了。

由于不是闭合回路，我们无法用括号序列来表示，因此我们用最小表示法，比如当前的轮廓线上，1,3,4 在一个连通块内， 6,7 在一个连通块内，我们可以用 (1011022) 来表示当前的轮廓线。不难证明一个数列与一个轮廓线的连通性是一一对应的。

由于 m\le 10 ，一条轮廓线上的不同的连通块个数最多有 6 个，所以我们使用 8 进制来表示这个数列。

来考虑怎么转移，发现有以下几种

此方格不选

若是保证 \rm dp 状态合法，左边的方块的连通性不变，上面的必须不是唯一的这个标号，不然上面的方块就变成一个独立的连通块了。若合法把上面的连通块标号改为 0 即可。

此方格选且左上至少有一个选

设标号分别为 A、B，那么需要 A、B 会连通成一个连通块（如果存在的话）。那么只需要把 \min(A,B) 以及 当前格点的标号改为 \max(A,B) 即可。不过如果 \min(A,B)=0 就没必要改了。

此方格选且左上都未选

最简单，只需要新建一个 7 号连通块即可。

经过上面的操作我们得到的并不是最小表示，只是单纯地连通性。我们需要简单地写一个函数使其变为最小表示。

为了方便起见，在转为最小表示的过程中，当且仅当只有一个连通块时状态才可以计入答案。

那么现在我们已经能计算最小值了。考虑构造方案。。

在原来的基础上，在 \rm dp 数组中记录每种状态的最大值的前一个状态，答案的结束状态、结束位置。这里用了个 pair 来实现。从结束位置向前遍历，并每次跳到前一个状态。

于是就可以愉快地A了这道题了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=11,INF=1000000;
int n,m,k,val[N][N];//为了强制选景点，赋极小值-INF
int mp[N][N];//在最优方案中这个值选不选
pair<int,pair<int,pair<int,int>>>ans;
#define Ans ans.first
#define endst ans.second.first
#define endx ans.second.second.first
#define endy ans.second.second.second
int bits[N],s[N];int x,y,nowans,nowst;
unordered_map<int,pair<int,int>>dp[N][N];
//规定：first为最小值， second为上一次状态
void init_bits(){for(int i=1;i<N;i++)bits[i]=i*3;}
void getstate(){for(int i=1;i<=m;i++)s[i]=(nowst>>bits[i])&7;s[0]=0;}
int relable(){
    static int t[20];memset(t,0,sizeof t);int cnt=0,st=0;
    for(int i=1;i<=m;i++)if(s[i]){
        if(t[s[i]])s[i]=t[s[i]];
        else s[i]=t[s[i]]=++cnt;
    }
    for(int i=1;i<=m;i++)st+=s[i]<<bits[i];
    if(cnt==1)ans=min(ans,{nowans,{st,{x,y}}});
    return st;
}
void insert(int st){
    if(dp[x][y].find(st)==dp[x][y].end())dp[x][y][st]={nowans,nowst};
    else dp[x][y][st]=min(dp[x][y][st],{nowans,nowst});
}
void DP(){
    dp[0][m][0]={0,0};
    for(x=1;x<=n;x++)
        for(y=1;y<=m;y++){
            int prex=x,prey=y-1;
            if(prey==0)prey=m,prex=x-1;
            for(auto k:dp[prex][prey]){
                nowst=k.first,nowans=k.second.first;
                //假装这里没有插头
                getstate();
                int d_plug=s[y],r_plug=s[y-1];
                int cnt=0;s[y]=0;
                for(int l=1;l<=m;l++)
                    if(d_plug==s[l])cnt++;
                if(!d_plug||cnt)insert(relable());
                //如果有插头
                getstate();
                nowans+=val[x][y];
                if(!r_plug&&!d_plug)s[y]=7;//新建连通块
                else{
                    s[y]=max(r_plug,d_plug);
                    for(int l=1;l<=n;l++)
                        if(s[l]&&s[l]==min(r_plug,d_plug))
                            s[l]=max(r_plug,d_plug);
                }
                insert(relable());
            }
        }
}
signed main(){
    scanf("%d%d",&n,&m);
    for(x=1;x<=n;x++)
        for(y=1;y<=m;y++)
            scanf("%d",&val[x][y]),val[x][y]==0&&(val[x][y]=-INF,k++);
    init_bits();DP();
    printf("%d\n",Ans+k*INF);
    nowst=endst;
    for(x=endx;x;x--){
        for(y=x==endx?endy:m;y;y--){
            if(nowst>>bits[y]&7)mp[x][y]=1;
            nowst=dp[x][y][nowst].second;
        }
    }
    for(x=1;x<=n;x++){
        for(y=1;y<=m;y++){
            if(val[x][y]==-INF)putchar('x');
            else if(mp[x][y])putchar('o');
            else putchar('_');
        }putchar('\n');
    }
}