P1448 [NOI1998] 围巾裁剪 题解

diamond_153 · 2023-03-24 13:16:13 · 题解

P1448 [NOI1998] 围巾裁剪 题解

看到这个题面，大家应该可以想到 dp。

我们先用 a[i][j] 存储点 (i,j) 是否被蛀虫咬坏，是为 0，不是为 1。

下一步我们设 a[i][j](2\nmid j) 表示从点 (i,j) 开始，最多可以向下延伸出一个没有任何小三角形被蛀虫咬坏，边长为 a[i][j] 的正三角形。我们可以得到：

以此类推，a[i][j](2\mid j) 表示从点 (i,j) 开始，最多可以向上延伸出一个没有任何小三角形被蛀虫咬坏，边长为 a[i][j] 的正三角形。我们可以得到：

由此，我们可以写出这一部分的代码：

for(int i=n-1;i;i--)
    for(int j=1;j<=i;j++)
        if(a[i][(j<<1)-1]&&a[i+1][(j<<1)-1]
                &&a[i+1][j<<1]&&a[i+1][(j<<1)+1]){
            a[i][(j<<1)-1]=min(a[i+1][(j<<1)-1],
                    a[i+1][(j<<1)+1])+1;
        }
for(int i=2;i<=n;i++)
    for(int j=2;j<i-1;j++)
        if(a[i][j<<1]&&a[i-1][(j<<1)-2]
                &&a[i-1][(j<<1)-1]&&a[i-1][j<<1]){
            a[i][j<<1]=min(a[i-1][(j<<1)-2],
                    a[i-1][j<<1])+1;
        }

下一步，我们枚举一条分割线 i，将围巾分成两个部分：一个为顶点在最上方且边长为 i 的正三角形，一个为剩余部分，使最终割下来的两个三角形一个在第一部分，一个在第二部分。然后就可以去枚举两个值 x,y，x 为第一个三角形的最大面积；y 为第二个三角形的最大面积。

我们就能通过枚举，得到每个分割线上下三角形面积和的最大值，代码如下：

int x=0,y=0;
for(int i=1;i<=n;i++){
    x=y=0;
    for(int j=1;j<=i;j++){
        for(int k=1;k<=j;k++)
            x=max(x,min(i-j+1,a[j][(k<<1)-1]));
        for(int k=1;k<j;k++)
            x=max(x,a[j][k<<1]);
    }
    for(int j=i+1;j<=n;j++){
        for(int k=1;k<=j;k++)
            y=max(y,a[j][(k<<1)-1]);
        for(int k=1;k<j;k++)
            y=max(y,min(j-i,a[j][k<<1]));
    }
    if(x&&y)ans=max(ans,x*x+y*y); //注意，x和y必须不为0
}

但是，这题我们还没做完，因为我们还没有考虑到下面这个情况：

注：棕色为最大选取部分。

所以，我们应该把这个围巾旋转 120°，再继续 dp，当我们把三种情况都考虑完时，这个题目就做完了。

旋转部分代码：

void rotate(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
            temp[n-i+j][((n-i)<<1)+1]=a[i][(j<<1)-1]?1:0; //旋转尖端朝上的小三角形
        for(int j=1;j<i;j++)
            temp[n-i+j+1][(n-i+1)<<1]=a[i][j<<1]?1:0; //旋转尖端朝下的小三角形
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=(i<<1)-1;j++)
            a[i][j]=temp[i][j]; //将旋转后的围巾拷贝到a里
}

完整代码：

#include<iostream>
using namespace std;
int n,m,ans=0;
int a[110][210]={0},temp[110][210]={0};
void calculate(){
    for(int i=n-1;i;i--)
        for(int j=1;j<=i;j++)
            if(a[i][(j<<1)-1]&&a[i+1][(j<<1)-1]
                    &&a[i+1][j<<1]&&a[i+1][(j<<1)+1]){
                a[i][(j<<1)-1]=min(a[i+1][(j<<1)-1],
                        a[i+1][(j<<1)+1])+1;
            }
    for(int i=2;i<=n;i++)
        for(int j=2;j<i-1;j++)
            if(a[i][j<<1]&&a[i-1][(j<<1)-2]
                    &&a[i-1][(j<<1)-1]&&a[i-1][j<<1]){
                a[i][j<<1]=min(a[i-1][(j<<1)-2],
                        a[i-1][j<<1])+1;
            }
    int x=0,y=0;
    for(int i=1;i<=n;i++){
        x=y=0;
        for(int j=1;j<=i;j++){
            for(int k=1;k<=j;k++)
                x=max(x,min(i-j+1,a[j][(k<<1)-1]));
            for(int k=1;k<j;k++)
                x=max(x,a[j][k<<1]);
        }
        for(int j=i+1;j<=n;j++){
            for(int k=1;k<=j;k++)
                y=max(y,a[j][(k<<1)-1]);
            for(int k=1;k<j;k++)
                y=max(y,min(j-i,a[j][k<<1]));
        }
        if(x&&y)ans=max(ans,x*x+y*y);
    }
}
void rotate(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
            temp[n-i+j][((n-i)<<1)+1]=a[i][(j<<1)-1]?1:0;
        for(int j=1;j<i;j++)
            temp[n-i+j+1][(n-i+1)<<1]=a[i][j<<1]?1:0;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=(i<<1)-1;j++)
            a[i][j]=temp[i][j];
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=(i<<1)-1;j++)
            a[i][j]=1;
    for(int i=0,x,y;i<m;i++){
        cin>>x>>y;
        a[x][y]=0;
    }
    for(int i=0;i<3;i++){
        calculate();
        if(i!=2)rotate();
    }
    cout<<ans;
}

注： a<<1 是在 a 为整数时，a*2 的等价形式。