[Noi2013]书法家

来自FallDream的博客，未经允许，请勿转载，谢谢。

小E同学非常喜欢书法，他听说NOI2013已经开始了，想题一幅“NOI”的字送给大家。

小E有一张非常神奇的纸，纸可以用一个n 行m 列的二维方格矩阵来表示，为了描述方便，我们定义矩阵左下角方格坐标为(1,1) ，右上角方格坐标为(m,n) 。矩阵的每个方格有一个整数的幸运值。在格子上面写字可以增加大家的幸运度，幸运度的大小恰好是所有被笔写到的方格的幸运值之和。现在你要在上面写上 ‘N’，‘O’，‘I’三个字母。

下面给出3个书法字的定义：

1.‘N’由若干（≥3）个边平行于坐标轴的矩形组成，设有K个矩形组成（标号1~K），第i个矩形的左下角方格坐标设为(Li ,Bi) ，右上角坐标设为(Ri ,Ti) ，要求满足：
a)Li<=Ri,Bi<=Ti
b)对任意1<i<=K，有Li=R(i-1)+1
c)对任意3<=i<K，有B(i-1)-1<=Ti<=T(i-1),Bi<=B(i-1);"
d)B2>B1,T2=T1,B(K-1)=B(K),T(k-1)<T(K)

2.‘O’由一个大矩形A，挖去一个小矩形B得到，这两个矩形的边都平行于坐标轴。设大矩形左下角的方格坐标为(u,v)，长为W宽为H，则小矩形B满足左下角方格坐标为(u+1,v+1) ，长W-2 ，宽H-2。要求满足：
a)W>=3,H>=3
b)u>R(K)+1

3.‘I’为3个边平行于坐标轴的从下到上的实心矩形组成，从下到上依次标号为1,2,3，第i 个矩形的左下角格子坐标设为(Pi , Qi )，右上角格子坐标设为(Gi , Hi )，要求满足：
a)Pi<=Gi,Qi<=Hi
b)P1=P3>u+W,G1=G3
c)Q1=H1=Q2-1,H2+1=Q3=H3
d)P1<P2<=G2<G1

下图是一个‘N’,‘O’,‘I’的例子

另外，所有画的图形均不允许超过纸张的边界。现在小E想要知道,他能画出的最大幸运度是多少。

n<=150 m<=500

可以按照列下来形状的不同分成11块（N分成3块，O分成3块，I分成3块，然后中间两个间隔）然后大力DP

N的处理比较复杂，可以开类似"一个坐标是x，另一个坐标大/小等于y的最大值"的dp数组来转移

#include<iostream>

#include<cstdio>

#include<cstring>

#define rint register int

#define INF 2000000000

#define N 150

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

int f1[][N+][N+],f2[][N+][N+],f3[][N+][N+],f4[],f5[][N+][N+],f6[][N+][N+],mx1[][N+][N+],mx3[][N+][N+];

int f7[][N+][N+],f8[],f9[][N+][N+],f10[][N+][N+],f11[][N+][N+],n,m,s[N+][],ans=-INF,mx2[][N+][N+];

inline void R(int&x,int y){y>x?x=y:;}

inline int sum(int x1,int y1,int x2,int y2){return s[x2][y2]+s[x1-][y1-]-s[x1-][y2]-s[x2][y1-];}

void Clear(int k)

{

    f4[k]=f8[k]=-INF;

    memset(f1[k],,sizeof(f1[k]));

    memset(f2[k],,sizeof(f2[k]));

    memset(f3[k],,sizeof(f3[k]));

    memset(f5[k],,sizeof(f5[k]));

    memset(f6[k],,sizeof(f6[k]));

    memset(f7[k],,sizeof(f7[k]));

    memset(f9[k],,sizeof(f9[k]));

    memset(f10[k],,sizeof(f10[k]));

    memset(f11[k],,sizeof(f11[k]));

    memset(mx1[k],,sizeof(mx1[k]));

    memset(mx2[k],,sizeof(mx2[k]));

    memset(mx3[k],,sizeof(mx3[k]));

}

int main()

{

    Clear();Clear();

    n=read();m=read();

    for(rint i=;i<=n;++i)

        for(rint j=;j<=m;++j)

            s[i][j]=read()+s[i-][j]+s[i][j-]-s[i-][j-];

    for(rint i=,a=,b=;i<=m;++i)

    {

        for(rint j=;j<=n;++j)

        {

            int Mx=mx3[b][j-][j-];

            for(rint k=j;k<=n;++k)

            {

                Mx=max(Mx,mx3[b][k][j]);

                int sum1=sum(j,i,k,i),sum2=sum(j,i,j,i)+sum(k,i,k,i);

                R(f1[a][j][k],max(f1[b][j][k],)+sum1);

                R(f2[a][j][k],mx1[b][j][k+]+sum1);

                R(f2[a][j][k],Mx+sum1);

                R(f3[a][j][k],mx2[b][k][j+]+sum1);

                R(f3[a][j][k],f3[b][j][k]+sum1);

                R(f4[a],f3[b][j][k]);

                R(f4[a],f4[b]);R(f8[a],f8[b]);

                R(f8[a],f7[b][j][k]);

                if(j+<k)

                {

                    R(f5[a][j][k],f4[b]+sum1);

                    R(f6[a][j][k],max(f6[b][j][k],f5[b][j][k])+sum2);

                    R(f7[a][j][k],f6[b][j][k]+sum1);

                    R(f9[a][j][k],max(f8[b],f9[b][j][k])+sum2);

                    R(f10[a][j][k],max(f9[b][j][k],f10[b][j][k])+sum1);

                    R(f11[a][j][k],max(f11[b][j][k],f10[b][j][k])+sum2);

                }

                R(ans,f11[a][j][k]);

            }

        }

        for(rint j=;j<=n;++j)

            for(rint k=n;k>=j;--k)

                mx1[a][j][k]=max(mx1[a][j][k+],f1[a][j][k]);

        for(rint j=n;j;--j)

            for(rint k=j;k;--k)

                mx2[a][j][k]=max(mx2[a][j][k+],f2[a][k][j]);

        for(rint j=;j<=n;j++)

            for(rint k=;k<=j;++k)

                mx3[a][j][k]=max(mx3[a][j][k-],f2[a][k][j]);

        swap(a,b);Clear(a);

    }

    printf("%d\n",ans);

    return ;

}

巴特西

[Noi2013]书法家

最新文章

热门文章