Codeforces Round #264 (Div. 2) C Gargari and Bishops 【暴力】

亦凉 2022-08-11 16:41 77阅读 0赞

题目：

题意：给出一个矩阵，每一格都有一个数字，然后放入两个象，想可以吃掉对角线上所有的数字，问两个象能吃掉的最大值。

分析：这个题目思路就是暴力，暴力计算出每一格放象的话能得到多少钱，然后求出两个不冲突的最大值，我比赛的时候写的方法是先求出每一个值，编号之后存到数组里面，然后在通过一系列处理得到，总之很麻烦，写了一个多小时，最后才发现有一点小错误，没时间了。初始样例也没有通过。

然后看了下别人写的，太简洁了。直接用行和列和和差就可以直接求出来。看来代码能力还非常有待提高啊。

我的AC代码：

#include <cstdio>
    #include <iostream>
    #include <queue>
    #include <cstring>
    #include <algorithm>
    #include <stack>
    #include <vector>
    #include <utility>
    #include <cmath>
    using namespace std;
    
    const long long N = 2200;
    long long mp[N][N],num[N][N];
    vector<long long> sum1,sum2;
    long long n;
    int main()
    {
        //freopen("Input.txt","r",stdin);
        while(~scanf("%lld",&n))
        {
            for(long long i=1; i<=n; i++)
            {
                for(long long j=1; j<=n; j++)
                    scanf("%lld",&mp[i][j]);
            }
            for(long long i=n; i>=1; i--)
            {
                long long tmp=0;
                for(long long x=1,y=i; x<=n; x++,y++)
                {
                    tmp+=mp[x][y];
                }
                sum1.push_back(tmp);
            }
            for(long long i=2; i<=n; i++)
            {
                long long tmp=0;
                for(long long x=i,y=1; x<=n; x++,y++)
                    tmp+=mp[x][y];
                sum1.push_back(tmp);
            }
    
            for(long long i=1; i<=n; i++)
            {
                long long tmp=0;
                for(long long x=i,y=1; x>=1; x--,y++)
                {
                    tmp+=mp[x][y];
                }
                sum2.push_back(tmp);
            }
            for(long long i=2; i<=n; i++)
            {
                long long tmp=0;
                for(long long x=n,y=i; y<=n; x--,y++)
                    tmp+=mp[x][y];
                sum2.push_back(tmp);
            }
            memset(num,0,sizeof(num));
            long long fx=1,fy=n;
            for(long long i=1;i<=n;i++)
            {
                long long xx=fx,yy=fy;
                for(long long j=1;j<=n;j++)
                {
                    num[i][j]=sum2[xx-1]+sum1[yy-1]-mp[i][j];
                    xx++,yy--;
                    //printf("%lld ",num[i][j]);
                }
                fx++,fy++;
            }
            long long ans[3]={-1,-1};
            long long x[3],y[3];
            for(long long i=1;i<=n;i++)
            {
                for(long long j=1;j<=n;j++)
                {
                    long long p=(i+j)%2;
                    if(num[i][j]>ans[p])
                    {
                        ans[p]=num[i][j];
                        x[p]=i,y[p]=j;
                    }
                }
            }
            printf("%lld\n",ans[0]+ans[1]);
            printf("%lld %lld %lld %lld\n",x[0],y[0],x[1],y[1]);
            sum1.clear(),sum2.clear();
        }
        return 0;
    }