当前位置：首页 > news >正文

打卡信奥刷题（3110）用C++实现信奥题 P7301 [USACO21JAN] Spaced Out S

news 2026/4/14 12:28:13

P7301 [USACO21JAN] Spaced Out S

题目描述

Farmer John 想要拍摄一张他的奶牛吃草的照片挂在墙上。草地可以用一个NNN行NNN列正方形方格所组成的方阵表示（想象一个N×NN \times NN×N的棋盘），其中2≤N≤10002 \leq N \leq 10002≤N≤1000。在 Farmer John 最近拍摄的照片中，他的奶牛们太过集中于草地上的某个区域。这一次，他想要确保他的奶牛们分散在整个草地上。于是他坚持如下的规则：

没有两头奶牛可以位于同一个方格。
所有2×22 \times 22×2的子矩阵（共有(N−1)×(N−1)(N-1) \times (N-1)(N−1)×(N−1)个）必须包含恰好 2 头奶牛。

例如，这一放置方式是合法的：

CCC ... CCC

而这一放置方式是不合法的，因为右下的2×22 \times 22×2正方形区域仅包含 1 头奶牛：

C.C .C. C..

没有其他限制。你可以假设 Farmer John 有无限多的奶牛（根据以往的经验，这种假设似乎是正确的……）。

Farmer John 更希望某些方格中包含奶牛。具体地说，他相信如果方格(i,j)(i, j)(i,j)中放有一头奶牛，照片的美丽度会增加aija_{ij}aij（0≤aij≤10000 \leq a_{ij} \leq 10000≤aij≤1000）单位。

求合法的奶牛放置方式的最大总美丽度。

输入格式

输入的第一行包含NNN。以下NNN行每行包含NNN个整数。从上到下第iii行的第jjj个整数为aija_{ij}aij的值。

输出格式

输出一个整数，为得到的照片的最大美丽度。

输入输出样例 #1

输入 #1

4 3 3 1 1 1 1 3 1 3 3 1 1 1 1 3 3

输出 #1

说明/提示

在这个样例中，最大美丽度可以在如下放置方式时达到：

CC.. ..CC CC.. ..CC

这种放置方式的美丽度为3+3+3+1+3+3+3+3=223 + 3 + 3 + 1 + 3 + 3 + 3 + 3 = 223+3+3+1+3+3+3+3=22。

测试点性质：

测试点 2-4 满足N≤4N \le 4N≤4。
测试点 5-10 满足N≤10N\le 10N≤10。
测试点 11-20 满足N≤1000N \le 1000N≤1000。

供题：Hankai Zhang，Danny Mittal

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1010,M=10010,INF=0x3f3f3f3f;inlineintMax(intx,inty){returnx>y?x:y;}inlineintMin(intx,inty){returnx<y?x:y;}inlinevoidSwap(int&x,int&y){x^=y^=x^=y;}intn,ans1,ans2,a[N][N];intline_sum(intj,inttype){intres[2]={0,0};for(inti=1;i<=n;i++)res[i&1]+=a[i][j];returnres[type];}introw_sum(inti,inttype){intres[2]={0,0};for(intj=1;j<=n;j++)res[j&1]+=a[i][j];returnres[type];}intmain(){scanf("%d",&n);for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)scanf("%d",&a[i][j]);for(intk=1;k<=n;k++){if(line_sum(k,0)>line_sum(k,1))ans1+=line_sum(k,0);elseans1+=line_sum(k,1);}for(intk=1;k<=n;k++){if(row_sum(k,0)>row_sum(k,1))ans2+=row_sum(k,0);elseans2+=row_sum(k,1);}printf("%d\n",Max(ans1,ans2));return0;}