首页 > 代码库 > BZOJ 2595 游览计划（插头DP）

BZOJ 2595 游览计划（插头DP）

2024-07-08 23:46:42   223人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2595

题意：给出一个数字矩阵。求一个连通块包含所有的数字0且连通块内所有数字之和最小。

思路：对于每个格子，是0则必须要选。那么对于不选的格子（i,j）在什么时候可以不选呢？必须同时满足以下两个条件：

（1）(i,j)不是0；

（2）(i-1,j)不选或者(i-1,j)选了但是轮廓线上还有别的地方与(i-1,j)是一个连通块。

 

int Pre[105][N],op[105][N];struct node{    int head[mod],next[N],e,st[N],val[N];        void init()    {        clr(head,-1); e=0;    }        void add(int S,int K,int preSt,int flag,int t)    {        int x=S%mod;        int i;        for(i=head[x];i!=-1;i=next[i])        {            if(st[i]==S)             {                if(K<val[i])                 {                    val[i]=K;                    Pre[t][i]=preSt;                    op[t][i]=flag;                }                return;            }        }        Pre[t][e]=preSt;        op[t][e]=flag;                st[e]=S; val[e]=K; next[e]=head[x];         head[x]=e++;    }};node f[2];int pre,cur,a[15][15],n,m;int S[15];void decode(int st){    int i;    for(i=0;i<m;i++) S[i]=st&7,st>>=3;}int incode(){    int x=0,i,t=1;    int mp[8];    FOR0(i,8) mp[i]=-1;    mp[0]=0;    for(i=m-1;i>=0;i--)    {        if(mp[S[i]]==-1) mp[S[i]]=t++;        S[i]=mp[S[i]];        x=(x<<3)|S[i];    }    return x;}void tran(int x,int y){    int i;    for(i=0;i<m;i++) if(S[i]==y) S[i]=x;}void DP(int i,int j,int flag){    int x,y,k,t,st,cost,r=i*m+j;    int num,temp;    for(k=0;k<f[pre].e;k++)    {        st=f[pre].st[k];        cost=f[pre].val[k];                decode(st);        x=j==0?0:S[j-1];         y=i==0?0:S[j];                 if(!flag)        {            num=0;            FOR0(t,m) if(S[t]==y) num++;            if(S[j]==0||num>1)             {                temp=S[j]; S[j]=0;                f[cur].add(incode(),cost,k,0,r);                S[j]=temp;            }        }                if(x&&y) tran(x,y);        else if(x||y) S[j]=x+y;        else S[j]=7;        f[cur].add(incode(),cost+a[i][j],k,1,r);    }}char str[15][15];void DFS(int k,int x){    int i=x/m,j=x%m;    if(op[x][k]) str[i][j]=a[i][j]?‘o‘:‘x‘;    else str[i][j]=‘_‘;    if(x<0) return;    DFS(Pre[x][k],x-1);}int main(){    RD(n,m);    int i,j;    FOR0(i,n) FOR0(j,m) RD(a[i][j]);    pre=0; cur=1;    f[pre].init(); f[pre].add(0,0,0,0,0);    FOR0(i,n) FOR0(j,m)    {        f[cur].init();        if(a[i][j]) DP(i,j,0);        else DP(i,j,1);        swap(cur,pre);    }    int ans=INF,last;    FOR0(i,f[pre].e)    {        decode(f[pre].st[i]);        FOR0(j,m) if(S[j]>1) break;         if(j>=m&&f[pre].val[i]<ans)         {            ans=f[pre].val[i];            last=i;        }    }    PR(ans); DFS(last,n*m-1);    FOR0(i,n) str[i][m]=0,puts(str[i]);}

 

 

 


联系
我们