Leaf-Salix.github.io

my blog

View on GitHub

【学习笔记】悬线法(未完)

前言

遇到一道DP题不会做

题解有一篇是顾z大佬的(我喜欢这种大佬QAQ,看他的博客是真的能学到东西的)

说需要用悬线法写,于是干脆学一下QAQ

应用

满足条件的最大子矩阵(当然求最大正方形加个约束就行了

例题

个人感觉写几道题大概就能搞懂它QAQ

T1

P1169 [ZJOI2007]棋盘制作

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int n,m;
int ans1,ans2;
int a[N][N];
int l[N][N],r[N][N],up[N][N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",a[i]+j);
            l[i][j]=r[i][j]=j;
        }
    for(int i=1;i<=n;i++)
    {
        for(int j=2;j<=m;j++) if(a[i][j]!=a[i][j-1]) l[i][j]=l[i][j-1];
        for(int j=m-1;j>=1;j--) if(a[i][j]!=a[i][j+1]) r[i][j]=r[i][j+1];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            up[i][j]=1;
            if(i>1&&a[i][j]!=a[i-1][j])
            {
                l[i][j]=max(l[i][j],l[i-1][j]);
                r[i][j]=min(r[i][j],r[i-1][j]);
                up[i][j]=up[i-1][j]+1;
            }
            int a=r[i][j]-l[i][j]+1;
            int b=min(a,up[i][j]);
            ans1=max(ans1,b*b);
            ans2=max(ans2,a*up[i][j]);
        }
    printf("%d\n%d",ans1,ans2);
    return 0;
}

T2

P4147 玉蟾宫


tip:以上题目可用悬线法写,下面这种只求正方形的还有另一种写法


T3

P1387 最大正方形

T4

P2701 [USACO5.3]巨大的牛棚Big Barn

T5

P1736 创意吃鱼法