P2213 [USACO14MAR]懒惰的牛The Lazy Cow

P2213 [USACO14MAR]懒惰的牛The Lazy Cow_Sliver

最大化一个子矩阵的和。

我们如何去做，dp和贪心呀！

大体题意：给定一个正方形，然后在正方形中求出一个大小已经给定的倾斜45的子正方形。使得这个正方形内的元素和最大。

倾斜45度？

好像可以做，有点麻烦？

可以观察到，如果我们将一个已经计算好了的菱形进行平推一格，那么变动的元素只\(2\ast k-1\)(k为边长)。然后每次维护就可以了。

时间复杂度\(O(n^2k)\)

感觉是对的。可我就是不愿意写。那怎么办？

考虑将整个图形旋转45度。

这是样例:

这样子矩形就正过来了。然后就可以很容易的跑前缀和暴力了。时间复杂度\(O((2n)^2)\)。不对，好像更慢了。

空间范围小mua_{，瞎搞就过了呀。在能通过的范围上最大化收益mua}~~

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

using std::max;

using std::min;

const int maxn=540;

int base[maxn][maxn];

int New[maxn<<1][maxn<<1];

int main()

{

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

            scanf("%d",&base[i][j]);

    for(int K=2;K<=2*n;K++)

        for(int j=1;j<=n;j++)

            if(K-j>0&&K-j<=n)

            {

                int i=K-j;

                int A=K-1;

                int B=(n-A)+2*(j-1)+1;//规律

                New[A][B]=base[i][j];

            }

    n=n*2;k=k*2+1;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

            New[i][j]=New[i][j]+New[i-1][j]+New[i][j-1]-New[i-1][j-1];

    int ans=0;

    k=min(n,k);

    for(int i=k;i<=n;i++)

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

            ans=max(ans,New[i][j]-New[i-k][j]-New[i][j-k]+New[i-k][j-k]);

    printf("%d",ans);

}

巴特西

P2213 [USACO14MAR]懒惰的牛The Lazy Cow_Sliver

最新文章

热门文章