Codeforce 2194D

题目链接

Given a table of size n×m , where each cell contains either 0 or 1 . The task is to divide it into two parts with a cut that goes from the top left corner to the bottom right corner. The cut lines can only go right or down.

Let a be the number of ones in one part of the table after the cut, and b be the number of ones in the other part of the table. The goal is to maximize the value of a⋅b .

题意给出n*m的只含0和1的表，要我们得出一条切割方案，使得切割后的两部分的1的数量的乘积最大，且输出这个方案。要求切割只能从左上角开始，向下或向右切割，最终切到右下角。

求最大值是简单的。我们总能找到一个方法，使两部分的1数量相等或仅差一。故ans=⌊k2⌋⋅(k−⌊k2⌋) 用二维前缀和统计1出现的次数，方便使用。

		vector<vector<ll>> v(n+1, vector<ll>(m+1, 0));
        vector<vector<ll>> onesum(n+1, vector<ll>(m+1, 0));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>v[i][j];
                onesum[i][j]=onesum[i-1][j]+onesum[i][j-1]-onesum[i-1][j-1]+v[i][j];
            }
        }
        ll k=onesum[n][m];
        ll fina=(k>>1)*(k-(k>>1));
        cout<<fina<<endl;

至于方案，通过生活经验，不难发现： 为使得一刀切，一般只有这三种方案，符合题目的只有3（向左下）。借用cf原题解： 我们划分出上面一整块区域，使得这个部分1的个数刚好小于k/2，而多一行就正好大于k/2。设有i行，则i+1行就是剩下的k/2-sum(前i行)，最后形成如下：

        int r1=m,r2=0,d1=n,d2=0;
        bool need=true;
        for(int i=0;i<n;i++)// i从0开始包含总第一行就开始分割的情况
        {
            if(onesum[i][m]==(k>>1))// 前i行正好等于k/2的情况
            {
                d1=i;d2=n-i;
                r1=m;r2=0;
                need=false;// 此时不用单独跳下一行
                break;
            }
            else if(onesum[i][m]<(k>>1) && onesum[i+1][m]>(k>>1))
            {
                d1=i;d2=n-i-1;
                for(int j=1;j<=m;j++)
                {
                    if((rsum[i+1][m]-rsum[i+1][j])+onesum[i][m]==(k>>1))
                    {
                        r1=j;r2=m-j;    
                        break;
                    }
                }
                break;
            }
        }
        for(int i=0;i<d1;i++)cout<<'D';
        for(int i=0;i<r1;i++)cout<<'R';
        if(need) cout<<'D';
        for(int i=0;i<r2;i++)cout<<'R';
        for(int i=0;i<d2;i++)cout<<'D';
        cout<<endl;

因为运用到了单行前缀和，因此在输入时顺便计算上 总代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
// #define x first
// #define y second
#define endl '\n'

const int MOD=998244353;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        vector<vector<ll>> v(n+1, vector<ll>(m+1, 0));
        vector<vector<ll>> onesum(n+1, vector<ll>(m+1, 0));
        vector<vector<ll>> rsum(n+1, vector<ll>(m+1, 0));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>v[i][j];
                onesum[i][j]=onesum[i-1][j]+onesum[i][j-1]-onesum[i-1][j-1]+v[i][j];
                rsum[i][j]=rsum[i][j-1]+v[i][j];
                // cout<<onesum[i][j]<<' ';
            }
            // cout<<endl;
        }
        // cout<<onesum[n][m];
        ll k=onesum[n][m];
        ll fina=(k>>1)*(k-(k>>1));
        cout<<fina<<endl;
        int r1=m,r2=0,d1=n,d2=0;
        bool need=true;
        for(int i=0;i<n;i++)
        {
            if(onesum[i][m]==(k>>1))
            {
                d1=i;d2=n-i;
                r1=m;r2=0;
                need=false;
                break;
            }
            else if(onesum[i][m]<(k>>1) && onesum[i+1][m]>(k>>1))
            {
                d1=i;d2=n-i-1;
                for(int j=1;j<=m;j++)
                {
                    if((rsum[i+1][m]-rsum[i+1][j])+onesum[i][m]==(k>>1))
                    {
                        r1=j;r2=m-j;    
                        break;
                    }
                }
                break;
            }
        }
        // cout<<need<<endl;
        for(int i=0;i<d1;i++)cout<<'D';
        for(int i=0;i<r1;i++)cout<<'R';
        if(need) cout<<'D';
        for(int i=0;i<r2;i++)cout<<'R';
        for(int i=0;i<d2;i++)cout<<'D';
        cout<<endl;
    }
    return 0;
}