【题解】P7472 [NOI Online 2021 入门组] 吃豆人（待填坑）

断清秋 · 2021-03-27 18:40:30 · 个人记录

题目传送门

UPD：这个思路假了，等有时间再来补坑

NOI Online 2021 入门组 T2。

由于这个图是正方形，具有对称性，所以实际上只需要枚举从第一行每一个点出发的情况就行了，易证从其余点出发不会比第一行更优。

于是根据对称性，直接求出第一行出发的所有点中的最大值，把这条路径经过的所有点权值清零，然后按照这个方法重新算一遍最大值，将两个结果相加即可。

时间复杂度 O(n^2)。

代码：

#include<bits/stdc++.h>
#define ll long long
#define back return
#define ri register int
using namespace std;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    back x*f;
}
ll a[1005][1005],n,sum[1005],maxx=-1,maxxi;
int main()
{
    //freopen("pacman.in","r",stdin);
    //freopen("pacman.out","w",stdout);
    n=read();
    for(ri i=1;i<=n;i++)
        for(ri j=1;j<=n;j++)
            a[i][j]=read();
    for(ri i=1;i<=n;i++)
    {
        if(i==1)
            for(ri j=1;j<=n;j++)
                sum[i]+=a[j][j];
        else if(i==n)
            for(ri j=1;j<=n;j++)
                sum[i]+=a[j][n+1-j];
        else
        {
            int cnt=0;
            for(ri j=i;j<=n;j++)
                sum[i]+=(a[j][++cnt]+a[cnt][j]);
        }       
    }
    for(ri i=1;i<=n;i++)
        if(maxx<sum[i])
        {
            maxx=sum[i];
            maxxi=i;
        }
    if(maxxi==1)
        for(ri j=1;j<=n;j++)
            a[j][j]=0;
    else if(maxxi==n)
        for(ri j=1;j<=n;j++)
            a[j][n+1-j]=0;
    else
    {
        int cnt=0;
        for(ri j=maxxi;j<=n;j++)
            a[j][++cnt]=0,a[cnt][j]=0;
    }
    for(ri i=1;i<=n;i++)
        sum[i]=0;   
    for(ri i=1;i<=n;i++)
    {
        if(i==1)
            for(ri j=1;j<=n;j++)
                sum[i]+=a[j][j];
        else if(i==n)
            for(ri j=1;j<=n;j++)
                sum[i]+=a[j][n+1-j];
        else
        {
            int cnt=0;
            for(ri j=i;j<=n;j++)
                sum[i]+=(a[j][++cnt]+a[cnt][j]);
        }       
    }
    sort(sum+1,sum+n+1);
    cout<<maxx+sum[n]<<endl; 
    back 0;
}