[比赛][CF][预处理][问题本身的性质] codeforces 1060C Maximum Subrectangle

这场有点惨的过分了,怎么说呢。。。经过了这一段的训练感觉该提高一些了但是却还是这样子。。。继续努力吧

这个题卡了是最最难受的,因为从矩阵的角度考虑不管怎么样都搞不出来一个O(n3)的算法,无论如何都不可能,然 而 ,然 而!这题目根本就不用考虑矩阵。。。因为每一行每一列都是成比例的啊。。。光给个矩阵怎么可能n²算出来答案?很明显是跟题目数据自身的性质有关系的,然后自己就傻脸看了俩小时不知道怎么操作,呵呵,出发点就不对怎么可能算出来。。。

因为每一行都是成比例的,比例是bi,所以要求一个最大的不超过x的子矩阵,只需要枚举上下边然后给预处理出来的sb数组乘个上下边之差就可以了,小于x的操作可以用sb[x/(pa[j]-pa[i-1])]来操作。。。。。。所有的处理都极其暴力,但是因为所有的处理都是在a或者b的一维序列上进行的,所以暴力也是n²,如果脑子里只有那个矩阵的话怎么都不可能n²,因为他是个二维的。。
写错的地方的话是x可能会比pb[m]大,这时候只需要取到这个最大值就可以了。

#include
//#include
//#include

using namespace std;

typedef long long LL;
const int maxn=2e3+5;
const int mod=1e9+7;

LL sb[maxn*maxn];
LL a[maxn],b[maxn],pa[maxn],pb[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    LL x;
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        pa[i]=pa[i-1]+a[i];
    }

    for (int i=1;i<=m;i++)
    {
        cin>>b[i];
        pb[i]=pb[i-1]+b[i];
    }
    cin>>x;
    for (int i=1;i<=m;i++)
        for(int j=i;j<=m;j++)
        sb[pb[j]-pb[i-1]]=max(sb[pb[j]-pb[i-1]],j-i+1LL);
    for(int i=1;i<=pb[m];i++)
        sb[i]=max(sb[i],sb[i-1]);
    LL ans=0;
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j++)
        {
            LL cur=x/(pa[j]-pa[i-1]);
            if(cur>=pb[m])
                ans=max(ans,(j-i+1)*sb[pb[m]]);
            else
                ans=max(ans,(j-i+1)*sb[cur]);
        }

    cout<
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据