[HOJ 224]I. 棋盤

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

YA終於AC了
首先，前情提要請看這裡
我們知道，這張圖可以分成若干個互不相關的點群
經過觀察，我們發現，一個點要塗上1或-1，「只受旁邊的點影響」
因此，何不來個「插頭DP」呢？
要注意的是，這個插頭DP很特殊，因為奇數列和偶數列的情況要「分開處理」
實作方面，我先把點群壓縮變成類似A=1,B=1的形狀
然後紀錄(0,0)這個點有沒有在點群裡面(就是SOLVER.type，0代表有)
狀態如果沒設計好轉移會很複雜(也容易寫錯)
我是直接用map存狀態和最佳解
其中第i個bit代表第i行填的是-1或1，至於第幾列就要看奇偶性了
因此在第i行放置1(或-1)的價值就可以透過第i-1和i+1個bit來求出
每個點群的最佳解加起來，就是答案了
我在想這題的時候思路轉了很多彎，從貪心、策略、窮舉、集合枚舉、Dfs+剪枝、DP，一直到插頭DP
插頭DP的狀態也試了很多種，在處理奇數偶數時也吃了不少RE和WA
不過AC之後成就感超大www <3

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<map>
using namespace std;
const int INF=2147483647;
void getmax(int &a,const int b){if(b>a)a=b;}
void SetBit(int &s,const int i,const int v){if(v)s|=1<<i;else s&=~(1<<i);}
int GetBit(const int s,const int i){return (s&(1<<i))>>i;}
struct BorderLineSolver
{
    int data[30][30],type;
    void Clear(){for(int i=0;i<30;i++)for(int j=0;j<30;j++)data[i][j]=-2;}
    void Print()
    {
        printf("R=%d,C=%d,type=%d\n",R,C,type);
        for(int i=0;i<R;i++)
        {
            for(int j=0;j<C;j++)printf("%3d",data[i][j]);
            puts("");
        }
    }
    bool Try(const int s,const int row,const int col,const int color,int &t,int &score)
    {
        if(!(-1<=data[row][col]&&data[row][col]<=1))printf("(%d,%d)error=%d\n",row,col,data[row][col]);
        assert(-1<=data[row][col]&&data[row][col]<=1);
        if(data[row][col]==1-color*2)return false;
        t=s;
        SetBit(t,col,color),score=0;
        if(row==0)return true;
        else if((row&1)==type)
        {
            if(col-1>=0&&GetBit(s,col-1)!=color)score++;
            if(col+1<C&&GetBit(s,col+1)!=color)score++;
        }
        else
        {
            assert(col>=1);
            SetBit(t,0,0);
            if(GetBit(s,col-1)!=color)score++;
            if(col+1<C&&GetBit(s,col+1)!=color)score++;
        }
        if(col)SetBit(t,col-1,0);
        return true;
    }
    int R,C;
    map<int,int>DP[2];
    void Update(const int d,const int s,const int v)
    {
        auto it=DP[d].find(s);
        if(it==DP[d].end())DP[d][s]=v;
        else getmax(it->second,v);
    }
    int Solve()
    {
        assert(type==0||type==1);
        DP[0].clear(),DP[1].clear();
        int d=0;
        Update(d,0,0);
        for(int row=0,col=type;;col+=2,d^=1)
        {
            while(row<R&&col>=C)row++,col=(row&1?type^1:type);
            if(row==R)break;
//            printf("row=%d,col=%d\n",row,col);
            for(const auto &it:DP[d])
            {
                static int t,score;
                if(Try(it.first,row,col,0,t,score))Update(d^1,t,(it.second)+score);
                if(Try(it.first,row,col,1,t,score))Update(d^1,t,(it.second)+score);
            }
            DP[d].clear();
        }
        int ans=0;
        for(const auto it:DP[d])getmax(ans,it.second);
//        printf("ans=%d\n",ans);
        return ans;
    }
}SOLVER;
int N,M,A,B,GRID[30][30];
bool VIS[30][30];
int Fill(int *s,const int r,const int c)
{
    int cnt=c/B;
    for(int i=c;i<M;i+=2*B,cnt+=2)
    {
        if(r==-1)s[cnt]=(cnt&1);
        else s[cnt]=GRID[r][i],VIS[r][i]=true;
    }
    return cnt-1;
}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int testcase;scanf("%d",&testcase);
    while(testcase--)
    {
        scanf("%d%d%d%d",&N,&M,&A,&B);
        for(int i=0;i<N;i++)for(int j=0;j<M;j++)scanf("%d",&GRID[i][j]),VIS[i][j]=false;
        int ans=0;
        for(int i=0;i<N;i++)for(int j=0;j<M;j++)if(!VIS[i][j])
        {
            SOLVER.Clear();
            int &sr=SOLVER.R=0,&sc=SOLVER.C=0;
            SOLVER.type=j/B;
            for(int r=i;r<N;r+=A,sr++)
            {
                if(sr%2==0)getmax(sc,Fill(SOLVER.data[sr],r,j));
                else getmax(sc,Fill(SOLVER.data[sr],r,(j+B)%(2*B)));
            }
//            SOLVER.Print();
            ans+=SOLVER.Solve();
        }
        printf("%d\n",ans);
    }
    return 0;
}