【JZOJ5056】【GDSOI2017模拟4.13】黑白廣場

Description

東轉盤有一個黑白廣場，那是帕斯卡金最喜歡的地方。

傳說中，這個一望無際的廣場是個N行M列的網格圖，每個格子都有黑白中的一種顔色。帕斯卡金有一根纖細的魔杖，他可以選擇一個格子(i,j)，并且可以施加他僅有的兩種魔法(任意次數，也可以不操作)：

1. 翻轉(i,j)的顔色，以及翻轉相鄰格子的顔色

2. 翻轉相鄰格子的顔色(翻轉：黑色變成白色，白色變成黑色；相鄰：兩個格子有公共邊)

當然了，帕斯卡金魔力有限。你願意告訴披荊斬棘、掃蕩群魔的帕斯卡金如何施加最少次數的魔法讓黑白廣場變成純白廣場嗎。

Data Constraint

10%的資料滿足：N*M<=12

30%的資料滿足：N*M<=81

100%的資料滿足：N,M<=10

Solution

這題是輪廓線dp。我們設出狀态f[i][j][s]表示目前做第i行第j列，包括(i,j)的前m個點的3進制狀态為s，再前面的均翻為0的最小步數。3進制狀态中0表示沒翻過且目前為0，1表示沒翻過且目前為1，2表示在該點上進行了1次操作。由于一個點假如操作了且目前為1，我們一定可以改變方案，在步數不變的情況下使之變為0。然後我們目前做到(i,j+1)，我們可以根據(i,j)和(i-1,j+1)的狀态推斷出(i,j+1)的值，接下來有幾種轉移：

1、假如目前(i-1,j+1)為1，我們一定要在(i,j+1)進行操作，才能保證(i-1,j+1)改為0。

2、假如目前(i-1,j+1)為0，我們可以有2種轉移：

1：目前的點(i,j+1)毛都不幹

2：目前點(i,j+1)采用操作1和操作2

3、假如目前(i-1,j+1)為2，除為0的兩種操作外，我們可以轉移：采用操作。

Code

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=59050,maxn1=11;
int f[maxn1][maxn1][maxn],a[maxn1][maxn1],er[maxn];
int n,m,i,t,j,k,l,x,y,z,p,q,ans;
char s[maxn];
int main(){
    freopen("square.in","r",stdin);freopen("square.out","w",stdout);
    while (1){
    scanf("%d%d\n",&n,&m);
    if (!n) return 0;
    for (i=1;i<=n;i++){
        scanf("%s\n",s+1);
        for (j=1;j<=m;j++)
            a[i][j]=s[j]-48;
    }er[1]=1;
    for (i=2;i<=m+1;i++)
        er[i]=er[i-1]*3;
    p=er[m+1];
    memset(f,127,sizeof(f));f[1][1][(p-1)/3*3+a[1][1]]=0;f[1][1][(p-1)/3*3+1-a[1][1]]=2;f[1][1][p-1]=1;q=f[1][0][0];
    for (i=1;i<=n;i++){
        for (j=1;j<m;j++)
            for (k=0;k<p;k++){
                if (f[i][j][k]==q) continue;
                x=a[i][j+1];
                if (k%3==2) x^=1;if (k/er[m]==2&&i!=1) x^=1;
                if (k/er[m]==1){
                    t=k%er[m]*3+2;
                    if (k%3==0) t+=3;
                    else if (k%3==1) t-=3;
                    f[i][j+1][t]=min(f[i][j+1][t],f[i][j][k]+1);
                }else{
                    f[i][j+1][k%er[m]*3+x]=min(f[i][j+1][k%er[m]*3+x],f[i][j][k]);
                    f[i][j+1][k%er[m]*3+1-x]=min(f[i][j+1][k%er[m]*3+1-x],f[i][j][k]+2);
                    if (k/er[m]){
                        t=k%er[m]*3+2;
                        if (k%3==0) t+=3;
                        else if (k%3==1) t-=3;
                        f[i][j+1][t]=min(f[i][j+1][t],f[i][j][k]+1);
                    }
                }
            }
        if (i==n) continue;
        for (k=0;k<p;k++){
            if (f[i][m][k]==q) continue;
            x=a[i+1][1];
            if (k/er[m]==2) x^=1;
            if (k/er[m]==1) f[i+1][1][k%er[m]*3+2]=min(f[i+1][1][k%er[m]*3+2],f[i][j][k]+1);
            else{
                f[i+1][1][k%er[m]*3+x]=min(f[i+1][j][k%er[m]*3+x],f[i][j][k]);
                f[i+1][1][k%er[m]*3+1-x]=min(f[i+1][1][k%er[m]*3+1-x],f[i][j][k]+2);
                if (k/er[m]) f[i+1][1][k%er[m]*3+2]=min(f[i+1][1][k%er[m]*3+2],f[i][j][k]+1);
            }
        }
    }ans=q;
    for (i=0;i<p;i++){
        t=0;x=i;
        while (x){
            if (x%3==1) t++;
            x/=3;
        }
        if (t) continue;
        ans=min(ans,f[n][m][i]);
    }
    printf("%d\n",ans);
    }
}