wannafly挑戰賽2 C Butterfly

題目描述

給定一個n*m的矩陣，矩陣元素由X和O構成，請求出其中最大的由X構成的蝴蝶形狀。

由X構成的蝴蝶形狀的定義如下：

存在一個中心點，并且其往左上、左下、右上、右下四個方向擴充相同的長度（擴充的長度上都是X)，且左上頂點與左下頂點、右上頂點與右下頂點之間的格子全由X填充。我們不在意在蝴蝶形狀内部是X還是O。

例如：

    XOOOX

    XXOXX

    XOXOX

    XXOXX

    XOOOX

是一個X構成的蝴蝶形狀。

    X

也是。

而

    XOOX

    OXXO

    OXXO

    XOXX

不是（不存在中心點）。

輸入描述:

第一行兩個整數n, m表示矩陣的大小(1 <= n, m <= 2000)；
接下來n行，每行一個長度為m的字元串表示矩陣，矩陣元素保證由X和O構成。      

輸出描述:

一行一個整數表示最大的由X構成的蝴蝶形狀的對角線的長度。      

示例1

輸入

5 5
XOOOX
XXOXX
XOXOX
XXOXX
XOOOX      

輸出

5      

思路：

很巧妙的題目轉化方式！

首先O(nm)預處理三個量： 

dp[0][i][j]：從(i,j)的位置開始左下方向連續的X的個數。 

dp[1][i][j]：從(i,j)的位置開始向下連續的X的個數。 

dp[2][i][j]：從(i,j)的位置開始右下方向連續的X的個數。

考慮枚舉每一個蝴蝶形狀的左上角頂點位置(i,j)。 

則我們需要找到一個最大的k，使(i,k)為一個蝴蝶形狀的右上頂點位置。

當蝴蝶形狀合法時，k需要滿足的條件為：(蝴蝶形狀的長為k−j+1) 

1).min(dp[1][i][j],dp[2][i][j])>=k−j+1 

2).min(dp[0][i][k],dp[1][i][k])>=k−j+1 

3).k>=j

移項後得到： 

1).j<=k<=min(dp[1][i][j],dp[2][i][j])+j−1 

2).min(dp[0][i][k],dp[1][i][k])−k−1>=−j

因為需要最大化k，故可以考慮用線段樹維護，對于每一個k，線段樹的相應節點儲存min(dp[0][i][k],dp[1][i][k])−k−1。故題目便轉化成了在區間(j,min(dp[1][i][j],dp[2][i][j])+j−1)中找到最大的下标使其維護的值>=−j。

因為蝴蝶形狀有中心點，故長度k−j+1一定為奇數，需要兩個線段樹，對于奇偶性不同的k分開維護。 原址：點選打開連結

代碼：

#include<bits/stdc++.h>
#define N 2005
using namespace std;
const int inf=1e9+7;
char s[N][N];
int dp[N][N][3];
struct Tree{
    int tree[N*4];
    void build(int l,int r,int p)
    {
        tree[p]=-inf;
        if(l==r)return;
        int m=l+r>>1;
        build(l,m,p<<1);
        build(m+1,r,p<<1|1);
    }
    void update(int l,int r,int p,int x,int y)
    {
        if(l==r){
            tree[p]=y;
            return;
        }
        int mid=l+r>>1;
        if(x<=mid)update(l,mid,p<<1,x,y);
        else update(mid+1,r,p<<1|1,x,y);
        tree[p]=max(tree[p<<1],tree[p<<1|1]);
    }
    int query(int l,int r,int x,int L,int R,int p)
    {
        if(L==R)return R;
        int mid=L+R>>1,ans=0;
        if(r>mid&&tree[p<<1|1]>=x)
            ans=max(ans,query(l,r,x,mid+1,R,p<<1|1));
        if(l<=mid&&tree[p<<1]>=x)
            ans=max(ans,query(l,r,x,L,mid,p<<1));
        return ans;
    }
};
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    for(int i=n;i;i--){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='X'){
                dp[i][j][0]=dp[i+1][j-1][0]+1;
                dp[i][j][1]=dp[i+1][j][1]+1;
                dp[i][j][2]=dp[i+1][j+1][2]+1;
            }
        }
    }
    int ans=0;
    Tree t1,t2;
    for(int i=1;i<=n;i++){
        t1.build(1,m,1);
        t2.build(1,m,1);
        for(int j=1;j<=m;j++){
            if(j&1)t1.update(1,m,1,j,min(dp[i][j][0],dp[i][j][1])-j-1);
            else t2.update(1,m,1,j,min(dp[i][j][0],dp[i][j][1])-j-1);
        }
        for(int j=1;j<=m;j++){
            if(s[i][j]!='X')continue;
            int x=min(dp[i][j][1],dp[i][j][2]);
            if(x<=ans)continue;
            if(j&1)x=t1.query(j,x+j-1,-j,1,m,1);
            else x=t2.query(j,x+j-1,-j,1,m,1);
            ans=max(ans,x-j+1);
        }
    }
    printf("%d\n",ans);
    return 0;
}